ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (6): 1185-1197.doi: 10.7544/issn1000-1239.2017.20160891

所属专题: 2017优青专题

• 人工智能 • 上一篇    下一篇

基于概率分布的多峰演化算法

陈伟能1,杨强1,2   

  1. 1(华南理工大学计算机科学与工程学院 广州 510006); 2(中山大学数据科学与计算机学院 广州 510006) (cschenwn@scut.edu.cn)
  • 出版日期: 2017-06-01
  • 基金资助: 
    国家自然科学基金优秀青年科学基金项目(61622206);国家自然科学基金面上项目(61379061)

Probability Distribution Based Evolutionary Computation Algorithms for Multimodal Optimization

Chen Weineng1, Yang Qiang1,2   

  1. 1(School of Computer Science and Engineering, South China University of Technology, Guangzhou 510006); 2(School of Data and Computer Science, Sun Yat-sen University, Guangzhou 510006)
  • Online: 2017-06-01

摘要: 演化算法通过模拟自然界生物迭代演化的智能现象来求解优化问题,因其不依赖于待解问题具体数学模型特性的优势,已成为求解复杂优化问题的重要方法.分布估计算法是一类新兴的演化算法,它通过估计种群中优势个体的分布状况建立概率模型并采样得到子代,具有良好的搜索多样性,且能通用于连续和离散空间的优化问题.为进一步推动基于概率分布思想的演化算法发展,概述了多峰优化演化算法的研究现状,并总结出2个基于概率分布的演化算法框架:面向多解优化的概率分布演化算法框架和基于概率分布的集合型离散演化算法框架.前者针对现有的演化算法在求解多峰多解的优化难题时缺乏足够的搜索多样性的缺点,将广义上基于概率分布的演化策略与小生境技术相结合,突破多解优化的搜索多样性瓶颈;后者围绕粒子群优化等部分演化算法在传统上局限于连续实数向量空间的不足,引入概率分布估计的思想,在离散的集合空间重定义了算法的演化操作,从而提高了算法的可用性.

关键词: 概率分布, 演化算法, 进化计算, 多峰优化, 计算智能

Abstract: Evolutionary computation (EC) is a category of algorithms which simulate the intelligent evolutionary behavior in nature for solving optimization problems. As EC algorithms do not rely on the mathematical characteristics of the problem model, they have been regarded as an important tool for complex optimization. Estimation of distribution algorithm (EDA) is a new class of EC algorithms, which works by constructing a probability model to estimate the distribution of the predominant individuals in the population, and sampling new individuals based on the probability model. With this probability-based search behavior, EDA is good at maintaining sufficient search diversity, and is applicable in both continuous and discrete search space. In order to promote the research of probability-based EC (PBEC) algorithms, this paper gives a survey on EC algorithms for multimodal optimization, and then further builds two frameworks for PBEC: PBEC framework for seeking multiple solutions in multimodal optimization, and PBEC framework for discrete optimization. The first framework presents a method to combine probability-based evolutionary operators with the niching strategy, so that higher search diversity can be maintained for seeking multiple solutions in multimodal optimization. In particular, the framework understands PBEC algorithms in a broad sense, that is, it allows both explicit PBEC algorithms (e.g. EDA) and implicit PBEC algorithms (e.g. ant colony optimization) to operate in the framework, resulting in two representative algorithms: multimodal EDA (MEDA) and adaptive multimodal ant colony optimization (AM-ACO). The second framework aims at extending the applicability of EC algorithms on both continuous and discrete space. Since some popular EC algorithms are originally defined on continuous real vector space and they cannot be directly used to solve discrete optimization problems, this framework introduces the idea of probability distribution based evolution and redefines their evolutionary operators on discrete set space. As a result, the applicability of these algorithms can be significantly improved.

Key words: probability distribution, evolutionary algorithm (EA), evolutionary computation (EC), multimodal optimization, computational intelligence

中图分类号: