【作者】 李振华；

【导师】 刘海林；

【作者基本信息】 广东工业大学 ， 应用数学， 2013， 硕士

【摘要】 概率模型进化算法是进化计算与统计学习理论相结合产生的一种新型进化算法。与传统进化算法相比,概率模型进化算法中没有使用交叉、变异等遗传操作,而是以概率模型的学习和采样来产生新的个体,实现种群的进化。进化多目标优化算法是进化计算领域最活跃的方向之一。在实际决策中,由于多目标优化问题不存在同时满足所有目标的最优解,因此需要决策者的偏好信息参与进化优化过程,使算法搜索更为有效。本文对概率模型进化算法多目标进化算法中的偏好选择问题进行了研究。概率模型进化算法依其理论来源主要有量子进化算法和分布估计算法两种。论文的主要工作和创新之处有：1.在考察量子计算基本原理的基础上,针对量子进化算法由于只使用量子旋转门进行更新造成的局部收敛问题,提出基于量子受控非门的量子染色体变异操作,增强算法的全局收敛能力。实验结果表明,新算法收敛性具有较大的改进。2.将核密度估计的方法引入到分布估计算法中,提出非参数型分布估计算法。通过核密度估计对当前种群的分布状况进行进行建模,不需要预先假定解的分布模型,而是只从种群本身出发获取解的分布特征,可以用来估计任意形状的密度函数。为了加速算法学习,进一步引入差分进化算法的思想,使种群向优良个体学习,并在变异中充分采用当前优良区域的整体信息。数值实验表明,新算法具有较好的收敛性能。3.将效用函数引入到多目标进化算法中,用于表示决策者对一个目标函数值的满意程度。证明了效用函数的单调性使得在将目标函数值映射到效用函数时,能够保持解之间的支配关系。进一步的,通过边际效用函数和目标函数之间的替代率的关系,阐明了算法所求得的解将聚集在决策者的偏好区域。数值试验表明,本文所提出的算法能够较好的得到决策者感兴趣区域的解。更多还原

【Abstract】 As a new type of evolutionary algorithm, probabilistic model based evolutionary algorithm derives from both evolutionary computation and statistical learning theory. Compared with the traditional evolutionary algorithms, probabilistic model based evolutionary algorithms do not use traditional genetic operation such as crossover and mutation. Instead, it uses the learning and sampling from probabilistic model to produce new individuals. In probabilistic model based evolutionary algorithm, statistical learning methods are used to build a probabilistic model from the macroscopic view of entire population to describe the distribution of the individuals. The new generation of population are generated by random sampling from the new probabilistic model. Since the probabilistic model is estimated by good individuals of the population, the new generated individuals will have better fitness than the previous generation. Therefore the population become evolutionary.Evolutionary multi-objective optimization algorithm is the most active topic of evolutionary computing. Since there is no single solution optimal all objectives simultaneously, preferences information from decision maker is necessary for multi-objective optimization evolutionary algorithm. The Preference information in evolutionary algorithm aims to make the search for preferred solutions more effective.This dissertation mainly focuses on probabilistic model based evolutionary algorithm: and preference based evolutionary multi-objective algorithm. Probabilistic model based evolutionary algorithm can be classified as quantum evolutionary algorithm and estimation of distribution algorithm by the theory origin. The main work and innovations are as follows:1. Based on the analysis of the basic concepts and principles in quantum computing, a quantum chromosome mutation operation is proposed based on quantum controlled not gate. This operation eliminates local convergence problem in the quantum evolutionary algorithm caused by just using the update method by quantum rotation gate, and enhances the global convergence performance of the algorithm. The experimental results show that the convergence performance of new algorithm has a great improvement.2. A non parameter distribution estimation algorithm by kernel density estimation is proposed. In this algorithm, the distribution of the current population is directly used to build up probabilistic model by kernel density estimation. This algorithm does not require any prior assumption of the distribution model of solutions. The distribution characteristics can be obtained from individual species itself which are used to estimate the probabilistic density function of arbitrary shapes without distribution assumption. In order to improve the convergence performance, the differential evolution algorithm is introduced to learn from the excellent individuals. And overall information in current excellent area can be used by mutation of individuals to generate more excellent individuals at greater probabilistic Numerical experiments show that the new algorithm has better convergence performance.3. The utility functions are introduced into evolutionary multi-objective algorithm to quantify decision makers’ satisfaction on an objective value. The domination between solutions maintains is proved when the objective functions are mapped to utility functions. The utility functions are aggregated by total utility and then integrated into SMS-EMOA, an hypervolume based evolutionary algorithm. Furthermore, the solutions generated by this algorithm will located in the interesting area through the relationship between the marginal utility function. Numerical experiments show that the algorithm can produce better solutions in decision maker’s interested regions.更多还原