【作者】 张欣；

【导师】 殷明浩；

【作者基本信息】 东北师范大学 ， 计算机软件与理论， 2017， 硕士

【摘要】 在工业生产、物流运输、科学研究以及日常生活中,人们总是为完成某些目标而寻求最优的解决方案,这些问题演化出种类繁多的复杂优化问题。根据解的取值范围,最优化问题可分为组合优化问题和函数优化问题。由于计算量大、求解难度高,传统精确算法已不适用于求解这类问题。此时,模拟大自然智慧的进化算法应运而生,这类算法模仿群体进化过程,具有一定的全局搜索能力,并且不依赖问题特征,具有很好的通用性。本文将采用不同的进化算法来求解现实生活中常见的两种复杂优化问题:流水车间调度问题和函数优化问题。流水车间调度问题是组合优化问题的重要分支,其中,分布组装式置换流水车间调度问题的生产模式与其他流水车间调度问题的生产模式相比更为复杂,但在现实生产过程中更具应用价值,它主要包括两个阶段,即生产和组装。第一阶段负责在多个工厂中生产零件;第二阶段负责将零件组装成最终产品。本文采用基于局部搜索策略改进的遗传算法求解该问题。首先,算法根据贪心策略设计交配池,选择有前景的父母。为加快算法收敛,本文根据序列分类的不同设计不同的交叉策略:产品组装序列和零件分配序列采用单点交叉,零件处理序列采用贪心策略改进的交叉算子。最后,算法结合基于两种邻居结构设计的局部搜索策略改进后代,以提高开发能力。详尽的实验分析表明,本文提出的算法具有鲁棒性,并且超越现有算法。函数优化问题应用范围广泛,吸引了许多学者进行研究。其诸多求解方法之一的布谷鸟算法是一种新颖的进化算法,它善于求解复杂函数但收敛缓慢。另一个优化算法,协方差矩阵自适应进化策略可以通过自适应概率分布和累积的演化路径加快收敛,但它在复杂函数求解方面表现不佳。因此,本文结合二者优点,提出布谷鸟算法和协方差矩阵自适应进化策略的混合算法,记为CS_CMA。每次迭代开始,新种群利用之前的进化信息进行初始化。算法采用变量分布的协方差矩阵和随机化改进Lévy Flight和偏置随机游走策略。首先,算法通过改进的Lévy Flight生成参考向量donor,其次,donor和当前种群通过改进的偏置随机游走策略生成后代。最后,算法采用选择算子生成下一代。迭代过程中,参数通过成功的参数值自适应调整。为验证CS_CMA的性能,本文以CEC2008的七个高维函数和CEC2011的一个工程优化问题为实验数据,计算结果表明,CS_CMA优于其他对比算法。更多还原

【Abstract】 In industrial production,logistics transportation,scientific research and daily life,people always seek the optimal solution to achieve certain goals.These problems have formed a wide variety of complicated optimization problems.According to the value range of their solutions,optimization problems can be divided into combinational optimization and function optimization.Because of large calculating quantity and solving difficulty of these problems,the traditional exact algorithms are not suitable to solve these problems.At this point,evolutionary algorithms derived from the wisdom of nature are proposed.These algorithms imitate population evolution,having the ability to search globally,and they do not depend on characteristics of problems,with a good generality.This paper will use different evolutionary algorithms to solve two kinds of optimization problems in real life: flowshop scheduling problems and function optimization problems.Flowshop scheduling is an important branch of combinatorial optimization problems.Among,the production mode of distributed assembly permutation flowshop scheduling problem(DAPFSP)is more complicated in the real production process.It consists of two stages: production and assembly.The first stage is production in factories;the second stage is to assemble jobs into final products.This paper applies local search to improve genetic algorithm for solving the problem.First,the mating pool is designed based on greedy strategy,to choose promising parents.To accelerate the convergence rate,this paper designs different crossover strategies for different sequences: sequences of product assembly and job assignment apply single-point crossover,sequences of job processing use crossover operator improved by greedy strategy.At last,local search strategies based on two neighborhood structures are incorporated to enhance the exploitation capability.After the exhaustive computation and statistical analysis,we can observe that the proposed methods are robust and outperform the existing algorithms.Function optimization has a wide range of application and has attracted many researchers to study.Cuckoo search(CS)is an innovative evolutionary algorithm designed for these problems.It is skilled in handling complex functions but has a slow convergence rate.On the other hand,covariance matrix adaption evolution strategy(CMA_ES)can converge quickly by self-adaptation of the mutation distribution and cumulation of the evolution path;however,it has a bad performance in complicated functions.Therefore,a hybridization of CS and CMA_ES,CS_CMA,is devised in this paper.A new population is initialized with previous evolutions in iteration.Covariance matrix of variable distribution and randomization are used to improve Levy Flight and biased random wal.First,a referenced vector(donor)is generated by improved Levy Flight;then,improved biased random walk uses donor and current population to generate offsprings.At last,selection operator is applied to generate the next generation.During the evolutionary process,parameters are adjusted via successful values self-adaptively.To demonstrate the capability of CS_CMA,experiments were done through 7 high-dimensional functions from CEC2008 and an engineering optimization problem from CEC2011,and comparative results prove that CS_CMA is superior to other contestant algorithms.更多还原