论文部分内容阅读
多目标规划在解决现代经济和社会问题中起着重要的作用,是应用数学的一个新的活跃的学科。传统运筹学解决多目标规划问题虽然已有几十年的历史,但进化算法在处理多目标规划问题上更有其特有的优势。用进化算法解决多目标问题,成为了最近的一个热门研究领域。思维进化计算是模拟人类思维进步过程的一种新的进化算法。它针对遗传算法存在的问题,采用“趋同”和“异化”操作代替遗传算法的交叉和变异算子,具有多方面的优越性。鉴于思维进化计算相对于其它进化算法的优越性,本文研究基于思维进化技术求解多目标规划问题的方法,提出了一种多目标思维进化算法NSMEA。NSMEA通过对Pareto快速非劣分类的改进来计算个体的适应度,将多目标规划的Pareto有效性理论引入到思维进化计算。其基本思想是:在解空间散布一些个体,依据个体的适应度及密度信息选择一些最好的个体作为各子群体的初始散布中心(异化操作Ⅰ);各子群体在其散布中心周围按正态分布散布一些个体,从上一代的优胜者和新散布的个体中选取非被支配解作为子群体的优胜者,再在其周围进行散布,重复此过程直到子群体成熟为止(趋同操作);对所有子群体的优胜者赋适应度值,判断成熟子群体是否被释放,并调整未成熟子群体的散布中心,把非劣解作为当前全局最优解(异化操作Ⅱ)。这样趋同与异化操作相互作用,不断向Pareto最优前沿逼近。本文利用概率论的基本理论,对该算法进行了收敛性分析。给出了该算法依概率收敛和几乎处处收敛的定义。理论上证明了在一定的条件下,该算法趋同过程产生的优胜者序列几乎处处收敛于局部Pareto最优解集,趋同和异化操作相互作用保证非劣解序列几乎处处收敛到全局Pareto最优解集。最后,用数值实验验证了该算法的可行性和有效性。用凸的,非凸的,不连续的,不均匀的经典测试问题对本文算法进行测试,并与国际上一些优秀算法(主要与最优秀的算法之一NSGAⅡ)进行了比较。实验结果表明NSMEA在处理各种类型的多目标规划问题上都表现出了良好的性能,能够很好地演化出问题的Pareto最优前沿。并且在一些测试问题上NSMEA性能优于PAES,SPEA,NSGAⅡ,能够快速收敛到Pareto最优前沿,分布均匀,覆盖范围广,且能得到大量的解点。对于解空间维数高的测试问题,收敛速度较慢,但最终能够收敛到Pareto最优前沿,且在Pareto最优前沿上得到较多的解点。综上所述,NSMEA是一种能收敛到全局Pareto最优解集的有效的多目标思维进化算法。