K均值优化算法综述

科技信息　

坝代智雒优化算法昀研究综述　

柳州师范高等专科学校数学与计算机科学系　吴春梅　

［摘要］本文着重回顾了现代智能优化算法的发展历程，主要介绍了现代智能优化算法的基本概念，主要包括模拟退火算法、遗传　

算法、神经网络优化算法、蚁群算法、粒子群优化算法等，并阐述了其工作原理和特点，归纳了它们主要的应用方向，同时对智能计算　

方法的发展进行了展望。　

［关键词］现代智能优化算法　遗传算法神经网络优化算法　

０、引言　

随着优化理论的发展，一些新的智能算法得到了迅速发展和广泛　

应用，成为解决传统优化问题的新方法，如遗传算法、蚁群算法、粒子群　

算法等。这些算法大大丰富了现代优化技术，也为具有非线性、多极值　

等特点的复杂函数及组合优化问题提供了切实可行的解决方案。现代　

智能优化算法主要包括：模拟退火算法、遗传算法、神经网络优化算法、　

蚁群算法、粒子群优化算法。这些优化算法都是通过模拟揭示自然现　

象和过程来实现，其优点和机制的独特，引起了国内外专家学者的高度　

重视。以下对几种常用的现代智能优化算法作简要的概述，并对智能　

计算方法的发展进行了展望。　

１、现代智能优化算法的发展历程及基本概念　

１．１模拟退火算法（Ｓｉｍｕｌａｔｅｄ　Ａｎｎｅａｌｉｎｇ，ｓａ）　

模拟退火算法…的思想最早是由Ｍｅｔｒｏｐｏｌｉｓ（１９５３）提出的，１９８３年　

Ｋｉｒｋｐａｔｒｉｃｋ等人将其应用于组合优化。该算法来源于物理中固体退火　

过程与一般组合优化问题之间的相似性，是基于Ｍｅｕｔｃ　Ｃａｒｌｏ迭代求解　

策略的一种随机优化算法。ＳＡ算法的基本思想是从一给定初始解开　

始，在邻域中随机产生另一个解，接受准则允许目标函数在有限范围内　

变差，以一定概率接受较差的解。目前，已经证明ｓＡ是一种在局部最优　

解中能概率性地跳出并最终趋于全局最优，是依概率１收敛于全局最　

优解的优化方法。　

１．２遗传算法（Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ，ＧＡ）　

遗传算法　是一类模拟生物界自然选择、自然遗传机制和进化过程　

多目标优化进化算法比较综述　口刘玲源　摘要多目标优化是最优化领域的一个重要研究方　向，本文简要介绍了多目标优化的模型和几种多目标　优化的进化算法，并对算法进行了简要比较。　关键词多目标优化粒子群遗传算法蚁群算法　人工免疫系统　中图分类号：ＴＰ３９１　文献标识码：Ａ　一、背景　多目标优化（Ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ　ＯｐｔｉｍｉｚａＴｉｏｎＰｒｏｂｌｅｍ，ＭＯＰ）　是最优化的一个雨要分支，多目标问题中的各目标往往是有着　冲突性的，其解不唯一‘，如何获得最优解成为多目标优化的…　个难点，目前还没彳丁绝对成熟与实用性好的理论。近年来，粒　子群算法、遗传算法、蚁群算法、人工免疫系统、等现代技术也　被应用到多闷标优化中，使多目标优化方法取得很火进步。本　文将其中四种多日标优化的进化算法进行一个简单的介绍　１　比较。　二、不同算法介绍　（一）多目标遗传算法。　假定各目标的期望日标值与优先顺序已给定，从优先级最　高的于目标向量开始比较两目标向量的优劣　，从Ｆ｛标末满足　的子日标元素１＿＝ｆＩｆ分开始每一‘级子目标向量的优劣性比较，最后　‘级子Ｆ｛标向量巾的各Ｈ标分量要全部参与比较。给定一个　不可实现的期望日标ｒｕＪ量时，向量比较退化罕原始的Ｐａｒｅｔｏ排　序，所有目标元素都必须参与比较。算法运行过程巾，适应值　图景可由不断改变的期望目标值改变，种群可由此被引导并集　中　一一特定折巾区域。当前利　群中（基丁Ｐａｒｅｔｏ最优概念）优　于该解的其他解的个数决定利・群巾每一个向量解的排序。　（二）人工免疫系统　人：ｌ：免疫算法是［Ｊ然免疫系统在进化计算巾的一个应用，　将抗体定义为解，抗原定义为优化问题，抗原个数即为优化子　日标的个数。免疫算法具有保持个体多样性、搜索效率高、群　体优化、避免过０　收敛等优点。其通用的框架是：将优化问题　的可行解对应抗体，优化问题的目标函数对应抗原，Ｐａｒｅｔｏ最优　解被保存在记忆细胞集中，，｛：采取　利ｔ机制对记忆集进行不断　更新，进而获得分布均匀的Ｐａｒｅｔｏ最优解。　（三）多目标ＰｓＯ约束算法。　将粒子群优化算法运用于优化问题，关键是如何确定群体　个局最优位置ｐｂｅｓｔ和每个粒子的最优位置ｇｂｅｓｔ。由于多目　标优化问题并无单个的最优解，所以不能直接确定ｇｂｅｓｔ，ｐｂｅｓｔ。　ＰＳＯ算法的优势在于：第…，彳『着高效的搜索能力。第二，并行　地ｌ叫时搜索多个非劣解。第三，有着较好的通用性。ＰＳＯ算法　在处理多日标约爪优化问题时，主要是解决自身和群体最佳位　最，对于群体最佳位簧的选择，一是所得到的解要在Ｐａｒｅｔｏ边　界上具有一定得分敞性，二是要求算法收敛速度好。对于自身　最佳位簧的选择要求是通过较少的比较次数达到非劣解的更　新。ＰＳＯ算法在处理约束时，多采用惩罚函数法。　（四）多目标蚁群算法。　多目标蚁群算法的思想是：根据目标函数的数目将蚂蚁分　成若干子群体，为每个子群体分配…个目标函数，在其他子群　体优化结果的基础一ｔｚ通过Ｐａｒｅｔｏ过滤器来获得均衡解。基小　步骤如下：　１、转移概率：对每一个目标ｋ需要考虑一些信息素轨迹　，　在算法的每一代巾，每一只蚂蚁都计算一组权重ｐ　ｐ　，　，…，　ｐ　），并且同时使用启发式信息和信息素轨迹。　２、局部信息索更新：当每只蚂蚁走完ａｉ　边之后，对每个Ｈ　标ｋ我们采取更新：　ｔ　ｋ＝（１－－ｐ）＇ｔｉｊｋ＋ｐｚｏ　其中，＂Ｃｏ是初始信息索的值，ｐ是信息素扦发速率。　３、个局信息索更新：对每个目标ｋ，在当前代只埘产生最好　和第二好的解进行信息素更新，使用规则如下：　Ｔ　（１一ｐ）ｚ，ｊ　＋ｐ／Ｘ％　４、设置Ｐａｒｅｔｏ解集过滤器：　设簧Ｐａｒｅｔｏ解集过滤器来存放算法运行时产生的Ｐａｒｅｔｏ解。　三、结论　四种进化算的优缺点总结如下：　多目标遗化算法：有着良好的鲁棒性和优越性，在洲挤选　择算子时，限制种群人小使　｝｛ｊ拥挤比较过程，使算法失去了收　敛性。人工免疫系统：可以得剑优化问题的多个Ｐａｒｅｔｏ最优解，　算法运行缺乏稳定性。多目标ＰＳＯ约束算法：能够实现对多维　复杂　间的高效搜索，研究还处于起步阶段。多日标蚁群算法：　Ｐａｒｅｔｏ前沿均匀性以及Ｐａｒｅｔｏ解集多样性，早熟停滞　在拧制　参数难以确定。口　（作者单位：四川大学商学院）　参考文献：　【ｌ】马小姝传统多目标优化方法和多Ｆｔ标遗传算法的比较综述　电气传　动自动化。２０１０．　【２】谢涛，陈火旺多目标优化与决策问题的演化算法…．　Ｉ】陶工　科学，２００２．　【３】王鲁，罗婷，赵琳，段海峰．螭于遗传算法的多｝＝Ｉ标优化技术［Ｊ】科技　‘场，　２００９　【４】樊纪Ｉ１』。王经啦基于人工免疫系统的多目标优化算法的研究　福建『ｂ　脑２００８　【５】池元成，蔡围飙．基于蚁群算法的多Ｈ标优化…计算机　Ｉ　程，２００９．　【６】孔翔宇．基于蚁群算法的多目标优化问题研究【Ｊ】四川理工学院学报．　２０１０．　【７】薛洪波，伦淑娴粒子群算法在多目标优化ｔｆｔ的应用综述【Ｊ］渤海大学学　报．２００９．　［８】哭庆洪．粒子群优化算法段其应用综述［Ｊ】．微计算机信息．２０ｌＯ　决策。．俯皂Ｉ　１１　１　２０１３年第７期总第１０３期ｌ

第３７卷第７期　２０１０年７月　计算机　科学　Ｓｃｉｅｎｃｅ　Ｖｏｉ．３７　Ｎｏ．７　Ｊｕｌｙ　２０１０　

生物地理学优化算法综述　

王存睿　。　王楠楠　段晓东　张庆灵。　

（大连民族学院非线性信息技术研究所　大连１１６６００）　（东北大学系统科学研究所　沈阳１１０００４）２　

摘要生物地理学（Ｂｉｏｇｅｏｇｒａｐｈｙ）是一门研究自然界种群迁移机制的科学，Ｄａｎ　Ｓｉｍｏｎ用生物地理学的方法和机制　

来解决工程优化问题，提出了生物地理学优化算＂Ｘｅ（ＢＢＯ，ＢｉｏｇｅＯｇｒａｐｈｙ－Ｂａｓｅｄ　Ｏｐｔｉｍｉｚａｔｉｏｎ）。生物地理学优化算法以　

其独特的搜索机制和较好的性能在智能优化算法领域得到了广泛的关注。对生物地理学优化算法的设计原理、迁徙　模型、算法流程及相应迁移和突变操作进行了综述。通过ＢｔｇＯ算法在１４个基准函数下与传统算法，如遗传算法、蚁　

群算法和粒子群等优化算法的性能比较，表明生物地理学优化算法是有效的。论述了算法与传统优化算法之间的差　

异以及ＢＢＯ算法有待解决的问题。　

关键词优化算法，生物地理学优化算法，智能优化　中图法分类号ＴＰ１８　文献标识码Ａ　

Ｓｕｒｖｅｙ　ｏｆ　Ｂｉｏｇｅｏｇｒａｐｈｙ－ｂａｓｅｄ　Ｏｐｔｉｍｉｚａｔｉｏｎ　

ＷＡＮＧ　Ｃｕｎ－ｒｕｉ　’。ＷＡＮＧ　Ｎａｎ－ｎａｎ　ＤＵＡＮ　Ｘｉａｏ－ｄｏｎｇ　ＺＨＡＮＧ　Ｑｉｎｇ－ｌｉｎｇ￣　

（Ｔｈｅ　Ｒｅｓｅａｒｃｈ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｎｏｎｌｉｎｅａｒ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ，Ｄａｌｉａｎ　Ｎａｔｉｏｎａｌｉｔｉｅｓ　Ｕｎｉｖｅｒｓｉｔｙ，Ｄａｌｉａｎ　１１６６００，Ｃｈｉｎａ）　（Ｔｈｅ　Ｒｅｓｅａｒｃｈ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｓｙｓｔｅｍ　Ｓｃｉｅｎｃｅ，Ｎｏｒｔｈｅａｓｔｅｒｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈｅｎｙａｎｇ　１１０００４，Ｃｈｉｎａ）２　

Ａｂｓｔｒａｃｔ　Ｂｉｏｇｅｏｇｒａｐｈｙ　ｉｓ　ｔｈｅ　ｓｔｕｄｙ　ｏｆ　ｔｈｅ　ｇｅｏｇｒａｐｈｉｃａｌ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｏｆ　ｂｉｏｌｏｇｉｃａｌ　ｏｒｇａｎｉｓｍｓ，Ｐｒｏｆ．Ｄａｎ　Ｓｉｍｏｎ　ｔｏｏｋ　ｔｈｅ　

第 22卷 第 5期2023年 5月Vol. 22 No. 5May 2023软件导刊Software Guide

连续昂贵多目标优化问题综述

张峰，陈新中（中国电子科技集团公司第二十八研究所，江苏 南京 210007）摘要： 许多实际工程优化问题通常需要同时优化多个相互冲突的目标，并且目标函数的计算主要依赖十分耗时的仿真实验，此类问题一般可称为昂贵多目标优化问题。代理辅助进化算法通过使用机器学习方法建立代理模型，并辅助算法进行评估，因而使代理辅助进化算法成为解决此类问题的热门方法。根据问题规模大小将相关算法划分成两类，描述每类问题特点，分类梳理相关算法，并说明每个算法的优缺点，以便人们能直观地了解连续昂贵多目标优化问题研究进展，更好地开展后续研究工作。关键词： 多目标优化；昂贵多目标优化；代理辅助进化算法；代理模型；机器学习DOI：10.11907/rjdk.221626开放科学（资源服务）标识码（OSID）：中图分类号：TP18 文献标识码： A文章编号：1672-7800（2023）005-0248-05Survey of Continuous Expensive Multiobjective Optimization ProblemsZHANG Feng， CHEN Xin-zhong（The 28th Research Institute of China Electronics Technology Group Corporation， Nanjing 210007， China）Abstract： Many practical engineering optimization problems usually involve optimizing multiple conflicting objectives at the same time， and the calculation of the objective function mainly relies on time-consuming simulation experiments， such problems can generally be called ex‐pensive multiobjective optimization problems. Surrogate-assisted evolutionary algorithms use machine learning methods to build surrogate mod‐els and assist algorithms for evaluation， which makes surrogate-assisted evolutionary algorithms a popular method to solve such problems. Ac‐cording to the scale of the problem， the relevant algorithms are divided into two categories， the characteristics of each type of problem are de‐scribed， the related algorithms are classified and sorted out， and the advantages and disadvantages of each algorithm are explained， so that people can intuitively understand the research progress of continuous expensive multiobjective optimization problems and better carry out fol‐low-up research work.Key Words： multiobjective optimization； expensive multiobjective optimization； surrogate-assisted evolutionary algorithm； surrogate mod‐el； machine learning