On a Feasible-Infeasible Two-Population (FI-2Pop) genetic algorithm for constrained optimization: Distance tracing and no free lunch
On a Feasible-Infeasible Two-Population (FI-2Pop) genetic algorithm for constrained optimization: Distance tracing and no free lunch
复制标题
DOI：
10.1016/j.ejor.2007.06.028
复制
发表时间：
2008-10-16
影响因子：
6.4
通讯作者：
Wood, David Harlan
中科院分区：
文献类型：
--
作者：
Kirnbrough, Steven Orla;Koehler, Gary J.;Wood, David Harlan
我们探索了数据驱动的方法来深入了解双种群遗传算法（GA）的动态，该算法在约束优化问题的测试中是有效的。我们跟踪并比较一群可行解和另一群不可行解。选择并培育可行解，以提高其目标函数值。选择和培育不可行的解决方案以减少对约束的违反。种群间的杂交完全是间接的，也就是说，只有当它们的后代碰巧迁移到另一个种群时才会发生。我们引入了一种距离的经验度量，并将其应用于个体之间和种群质心之间来监测进化的进程。我们发现两个种群的质心彼此接近并趋于稳定。这是一个有价值的收敛特征。我们发现不可行种群影响，有时甚至支配最优解的遗传物质。由于不可行种群不被目标函数评估，因此可以自由地探索可能找到最优的边界区域。粗略地说，优化的无免费午餐定理表明，所有黑盒算法（如遗传算法）在所有问题集上具有相同的平均性能。因此，平均而言，我们的算法并不比随机搜索或任何其他黑箱搜索方法好。然而，对于我们研究的约束优化问题类，我们提供了两个一般定理，它们给出了使No Free Lunch结果为空的条件。因此，这里采取的方法本身就避开了“没有免费的午餐”的含义。(C) 2007年Elsevier B.V.出版
We explore data-driven methods for gaining insight into the dynamics of a two-population genetic algorithm (GA), which has been effective in tests on constrained optimization problems. We track and compare one population of feasible solutions and another population of infeasible solutions. Feasible solutions are selected and bred to improve their objective function values. Infeasible solutions are selected and bred to reduce their constraint violations. Interbreeding between populations is completely indirect, that is, only through their offspring that happen to migrate to the other population. We introduce an empirical measure of distance, and apply it between individuals and between population centroids to monitor the progress of evolution. We find that the centroids of the two populations approach each other and stabilize. This is a valuable characterization of convergence. We find the infeasible population influences, and sometimes dominates, the genetic material of the optimum solution. Since the infeasible population is not evaluated by the objective function, it is free to explore boundary regions, where the optimum is likely to be found. Roughly speaking, the No Free Lunch theorems for optimization show that all blackbox algorithms (such as Genetic Algorithms) have the same average performance over the set of all problems. As such, our algorithm would, on average, be no better than random search or any other blackbox search method.. However, we provide two general theorems that give conditions that render null the No Free Lunch results for the constrained optimization problem class we study. The approach taken here thereby escapes the No Free Lunch implications, per se. (C) 2007 Published by Elsevier B.V.