基于聚类的路径优化算法在工程科学与技术中的应用

工程科学与技术，国际期刊19（2016）2022完整文章一种新的基于聚类的路径优化上午Aibinua，H.Bello Salaub，Najeeb Arthur Rahmanc，M.N.Nwohud，C.M.阿卡楚库乌河a联邦理工大学机电工程系，P。M. B. 20，双子座，尼日利亚b联邦技术大学电信工程系，P。M. B. 20，双子座，尼日利亚c马来西亚国际伊斯兰大学电气和计算机工程系，P.O. Box 53100，Gombak，Malaysiad联邦技术大学电气和电子工程系，P。M. B. 20，双子座，尼日利亚e/尼日利亚阿提奇莱因福奥文章历史记录：2016年1月26日收到2016年7月7日修订2016年8月7日接受2016年8月21日在线发布保留字：聚类遗传算法种群控制路径优化选择A B S T R A C T遗传算法（Genetic Algorithm，GA）是一种模仿生物进化原理的随机通用进化搜索技术，已被广泛应用于解决人类各个领域的各种问题。尽管它的强度和广泛的应用范围，最佳的解决方案可能是不可行的情况下，涉及染色体选择交配和再生的生殖过程中没有正确地完成。此外，当染色体的适应度值存在显著差异时，使用基于概率的选择方法往往会遇到困难。在这项工作中，基于聚类的遗传算法与一夫多妻制和动态人口控制机制已被提出。从每一代染色体中获得的适合度值被聚类成两个不重叠的簇。选择的簇中的存活染色体进行一夫多妻交叉交配过程，而后代的群体将形成下一代进行动态的群体控制机制。重复该过程，直到实现收敛到全局解或经过若干代。该算法已被应用到路径优化问题。结果表明，该算法优于现有的一些技术.此外，所提出的算法收敛到全球解决方案在几次迭代（代），从而有利于其可接受的在线实时应用。通过引入基于聚类的选择算法，保证了在每一代中选择具有最优解此外，引入动态种群控制与多配偶选择过程，使快速收敛到最优解和多样性的人口分别。©2016 Karabuk University. Elsevier B.V.的出版服务。这是CCBY-NC-ND许可证（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍遗传算法（GA）是一种模仿自然生物进化原理的随机通用搜索技术[1约翰·霍兰德开创了遗传算法动力学的研究和初始相关理论的形成，从而导致了遗传算法在20世纪60年代的创新和发展[7根据图1所示的达尔文在每一代，通过选择可能的解决方案（个体）来生成一组新的解决方案，这些解决方案相对于问题区域内的适应度值[7这是通过应用*通讯作者。电 子邮 件地 址：maibinu@gmail.com ，Abiodun. futminna.edu.ng（ 上午 ）Aibinu）。从自然遗传学中借来的繁殖算子这一过程的结果是后代群体的进化，这些后代比他们的父母更适应他们的环境，并且在表现方面更好[10遗传算法使用概率规则来指导搜索和选择过程，从而降低了收敛到局部解的风险此外，这允许探索搜索空间中最有前途的领域。这是通过同时考虑搜索空间中的许多点来实现的，因此，有利于更适合的个体的交配[15]。因此，使GA成为一种有效和鲁棒的搜索算法，允许在大而复杂的搜索空间中快速定位高质量的解决方案区域[15，16，20]。GA在其他搜索算法中脱颖而出，并通过对个体群体进行工作来区分自己，每个个体代表问题的可能解决方案。适应度函数的计算、种群解的编码和解码、选择、繁殖和收敛是遗传算法的基本原理[7，8，20，16]。http://dx.doi.org/10.1016/j.jestch.2016.08.0032215-0986/©2016 Karabuk University.出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表工程科学与技术国际期刊杂志主页：www.elsevier.com/locate/jestchA.M. Aibinu等人/工程科学与技术，国际期刊19（2016）20222023Fig. 1. 达尔文GA相对于其他传统优化技术的其他优点包括：1. 易于理解的概念;在嘈杂的环境中使用鲁棒性[7];2. 易于并行运行;3. 在迭代之间改变或改变适应度函数的能力，从而便于在模型中纳入新数据（如果可用）;4. 支持多目标优化。此外，遗传算法已在各种工作中被证明有时会导致最优和全局解决方案[1，2，7，8]。遗传算法已被广泛应用于人类努力的各个领域，其中值得注意的是：电子电压振荡器设计[1，2]，数字信号处理[10，1,2，13]，焊接[14]，通信[15]，通信[16]，通信[17]，通信[18]，通信[19]，通信[阳离子[17，18]，农业[19]，发电[20]，金融[21]，机器人[22]，免疫系统[23]，检查时间表[24，25]，数字图像处理[26关于遗传算法在功率优化中的应用的详细综述载于[11]。本文的其余部分组织如下：审查GA选择过程中讨论的第2节;数学推导的建议的方法在第3节，而性能分析和讨论载于第4节。本文最后一节给出了结论和建议。2. 遗传算法选择过程综述在这一节中，遗传算法的繁殖过程的审查，重点是选择机制。性能比较表显示的缺点和优点的一些现有的遗传算法选择过程中也提出了在本节中。遗传算法繁殖过程中的一个关键过程是染色体选择方法。有人认为，该过程决定了算法的成功与否，因为它需要确定和选择哪些解决方案是好的，需要保留和复制。它确保了在每一代中只有最适者生存，而不适者在恒定的种群中被丢弃[3文献中存在许多GA选择方法，其中包括：1. 锦标赛选择2. 轮盘赌选择3. 秩选择4. 稳态选择轮盘赌轮选择（RWS）方法：是最流行的GA选择方法之一，其他一些选择技术也基于此[7-9]。父染色体是基于它们的适应值来选择的。在实现这一点时，根据每根弦的适合度，为每根弦标记轮盘周长轮盘旋转n次，每次选择一个由轮盘指针选择的字符串实例更好的染色体有更大的机会被选择，因为轮的周长是基于与串适应度函数成比例的串来标记的然而，当适应度值存在显著差异时会遇到困难[7，3此外，虽然选择是基于适应度值，但不能绝对保证会选择好的个体[3]。等级选择方法：等级选择技术是为了解决轮盘赌选择方法中遇到的问题而开发的。在RWS中，具有低适应度值的染色体具有最小的被选择的机会，并且适应度值的大因此，引入排序选择方法来解决这些问题[3，4]。在该方法中，个体染色体根据其适应度值进行排序，然后引入概率方法进行选择。这种排序方法引入了缓慢的收敛速度，有时会收敛到次优解，因为从一代到另一代可能会保留不太适合的染色体。锦标赛选择方法：在这种方法中，不同的巡回赛是在从人群中随机选择的几个人之间进行的。每个比赛的获胜者被选为下一代。比赛规模可以改变，以减轻选择压力的调整。然而，当锦标赛规模较大时，选择弱个体的机会比比皆是[3，5，4]。稳态选择法：稳态选择法涉及在每一代中通过少数好染色体产生新的后代。一些坏的染色体被移除，新的后代被用来取代坏的染色体。因此，其余的种群不经过选择过程就迁移到下一代表1中呈现了显示广泛已知的GA选择过程的优点和缺点的性能评估的总结。3. 基于多配偶繁殖和种群控制技术的聚类遗传算法在克服上述缺点，在现有的遗传算法的繁殖过程中表1，这项工作提出了基于聚类的遗传算法（CGA）与多配偶选择和动态人口控制技术。本文的主要贡献是在所提出的技术，克服了短期的轮盘赌轮，排名和精英主义的方法在GA选择过程中，通过最小化质心和个体染色体之间的距离，以改善搜索空间，而不是使用概率的方法与一些已知的选择技术的发展。引入一夫多妻制、动态种群控制和生育控制机制，使种群具有更大的多样性，从而提供了更好的解决方案，具有更快的收敛速度。所提出的CGA中的每个步骤的详细讨论在图1中的方法流程图中示出。 二、1. 参数设置所提出的CGA技术模拟了自然进化过程，即经历人口的增加或减少，●●●●2024A.M. Aibinu等人/工程科学与技术，国际期刊19（2016）2022ð Þð Þð Þ表1GA选择过程的比较表。没有类型优势劣势1轮盘赌选择2秩选择3锦标赛选择4稳态选择选择较优染色体的概率较高，实现所有染色体都有公平的机会被选择;高选择压力;与RWS锦标赛相比，更好的性能可以改变，以减轻选择压力的调整;保持多样性;不敏感性。边缘化弱染色体;适用于没有目标函数的情况这往往导致少数优良染色体产生新的后代当适应值存在显著差异时遇到困难;不能保证选择最适合的染色体;性质上的概率性;高随机变异性。可能导致收敛速度较慢，因为最好的染色体与其他染色体没有太大的差异;自然界如果比赛规模很大，弱个体有机会当选;自然界中的概率因此受到随机效应的影响;需要偏好排序;不能保证每个染色体都会出现在给定的vyvle它需要大量的迭代代此外，它没有与现有的和广泛已知的GA技术相关联的恒定种群，并且与传统GA技术中的六个不同参数的设置相比，仅需要设置四个参数。所需参数为：(a) 初始种群大小（N）(b) 最高人口增长率（r）(c) 突变率(c)世代数X与大多数现有的遗传算法不同，该算法可以从较低的初始种群规模N开始。最大种群增长率r允许种群大小从一代到一代的动态增加或减少，直到达到最大世代X，因此像正常的人类进化过程一样进化。人口增长率是使用随机数生成器生成每一代的增长率来实现的，其值从-r到10r不等。图二. 提出了一夫多妻制和人口控制机制的CGA。A.M. Aibinu等人/工程科学与技术，国际期刊19（2016）20222025X¼¼¼..2i1j1..如[35]中报告的，人群大小增加或减少的依据取决于人群的可用数据。数据表明，从一代到另一代的演变涉及人口变化，因此没有一个国家经历过几代人的人口静态增长。2. 基因编码与解码候选解（染色体）的初始群体大小N基于问题定义生成。染色体是候选解的抽象表示，候选解是变量（基因）串联的产物。对于路线优化相关问题，字符串的使用可适用于基因或染色体表示，而对于其他优化问题，二进制染色体的使用可能是适当的。均匀分布的方法已被采用的初始染色体产生。在MATLAB中，这可以使用rand（）内置函数来实现使用二进制染色体表示方法涉及编码和解码操作。可能的解决方案的变量（基因）转换为二进制形式。本工作采用了三阶段编码操作。(a) 基因/染色体编码第一阶段涉及确定最佳编码所需的适当位数，而第二阶段涉及确定编码操作的位步长。第三阶段涉及从整数到二进制字符串的转换。本文给出了这三个阶段的解释和数学符号i. 位数的确定二进制编码方案中的第一阶段是基于每个基因的预期分辨率确定所如果变量（基因）的域xi是[ai，bi]，并且所需的精度是小数点pi，则使用下式计算用于编码解值所需的位数mi：2mi-1bi-ai×10pi <2米i-1米1米ii. 步长和位置确定：一旦使用（1）确定了基因所需的位数mi，第二阶段就涉及确定适当的步长。步长D由下式获得：xi¼ai12月2日，i12 ×Di16日其中，bsi表示在域1/2ai;bi]内要被解码为十进制的编码的二进制染色体串;Di由（2）控制，并且bin2dec是二进制到十进制的转换器，给出为Mi12月2日bindik×2i7k¼13. 适应度函数评价一个解决方案的可取性量化的适应度函数，这是密切相关的优化过程的目标适应度水平用于评估所得染色体，因此使用适应度函数从染色体评估获得的值表征候选解决方案的适应性性能[16]。种群中染色体适应度的评价涉及到由目标函数约束的计算。目标函数通常表示为染色体中编码的变量或基因的函数。大多数优化问题都涉及到目标函数的最小化或最大化，因此需要使用两个质心聚类方法（即K2）。在这项工作中，最小化已被分配的聚类数，K1，而最大化被分配的聚类数K2，随后将用于染色体选择阶段。4. 再现操作在这项工作中，提出了一个三阶段的方法，包括聚类，一夫多妻制交配和人口控制过程所采用的聚类方法类似于K-Means技术，并且是一种非概率方法，其确保在每一代中选择最适合的染色体用于繁殖目的并增强种群的多样性。聚类方法在复制过程中引入了高选择压力，从而增加了平均代适应值，并增加了收敛速度，而不会由于选择了最适合的染色体的聚类而导致特定染色体的不确定性多配交配使选择产生的最适染色体享受多配生殖过程，从而将其某些特性传递给后代。最后一个阶段确保该代的人口不超过可接受的bi-ai2mi- 1ð2Þ通过控制生育或人口控制技术提高人口增长率。每个阶段的详细讨论都是预先准备的。在使用（2）确定适当的D时，使用下式随后发出(a) 遗传聚类选择技术两个质心聚类的选择确保了群体中的每个染色体属于FitterLi¼ xi-aið3Þ染色体簇（FCC）或不太适合的染色体簇-Dii.二进制位置到二进制转换：最后一级涉及使用mi个位从二进制位置Li到二进制的转换。在MATLAB中用于实现这一点的适当函数是dec2bin（Li，mi），因此bs¼dec2binLi;mi4表示基因的所得二进制串bs可以表示为BSI 1/4 d imdim-1dim-2.. . ：di2di15其中d_im是二进制整数。(b) 基因/染色体解码低森林覆盖率国家（LFCC）这种用于交配的染色体选择的二进制方法采用迭代算法，该算法在两个聚类上使从每个染色体到其聚类质心的距离之和最小化。染色体在簇之间移动，直到总和不再能进一步减少。这将导致一组尽可能密集和间隔良好的解决方案的集群。在典型的最大化操作中，选择具有较小距离的聚类中的染色体在数学上，设总点散布T对于N的集合第i代的染色体，对应的解码操作涉及映射NN从二进制字符串到实数。对变量的解码表十一被给定为T¼1XXdxi;xj8D¼i2026A.M. Aibinu等人/工程科学与技术，国际期刊19（2016）2022K¼ð Þ ¼-K其中dxi;xj是2条染色体之间的距离，因此（8）可以写成1XX0X X1从数学上讲，N1的高值将最终导致人口过剩，伴随着算法计算时间的增加，因此，人口控制与自然进化论已经提出。两种类型的人口骗局-T1/2k<$1Ci<$k@Cj¼k dxi;xjCjdxi;xjA 9在这项工作中，已经提出了控制，这是生育控制（BC）和人口增长率控制（PGRC）。因此，（9）可以概括为：T¼ W C B C10其中WC是类内分散距离，BC是聚类距离之间，Ci表示聚类数，第39话观察如果d<$xi;xj<$被认为是欧几里得距离，则WCXNkXkxi-mkk211k¼1Ci¼KCGA选择的实现可以概括为以下步骤：I.步骤1：随机生成2个初始染色体适应度i. 计划生育（BC）在BC方法中，已经提出了两种技术，即单后代和双后代。在单后代BC（SOBC）中，两个父代在交叉操作后仅允许产生单个后代，而在双后代BC（DOBC）方法中，两个父代被允许从交叉操作产生两个后代。ii. 种群增长率控制（PGRC）尽管引入了BC，但有时产生的后代的数量仍然高于预期或估计的数量，因此，或者从N01中随机选择N00chil-12值质心，即初始化C1;C2。ii. 步骤2：使用11将染色体的每个适应度值分配给具有更接近质心的组。iii. 步骤3：当染色体的适应度值被分配后，重新计算2-质心的位置。iv. 步骤4：重复步骤2和3，直到质心不再移动，染色体适应度值不改变聚类。这将染色体拟合值分成组，即FCC和LFCC。v. 步骤5：比较两个质心。vi. 步骤6：如果目标函数是基于最大化的，则具有较高数值的类质心被分配给FCC，而另一个聚类被分配给LFCC。类似地，如果目标函数是基于最小化的，则具有较低值的类质心被分配给FCC，而另一个被分配给LFCC。vii. 第七步：结束(b) 一夫多妻交配过程：聚类选择技术将选择操作的结果是更适合的染色体的数量从N减少到N1。最终的种群N1通常小于或等于原始种群，即N1

下载后可阅读完整内容，剩余1页未读，立即下载