One of the key difficulties in using estimation-of-distribution algorithms is choosing the population sizes appropriately: Too small values lead to genetic drift, which can cause enormous difficulties. In the regime w...
详细信息
ISBN:
(纸本)9781450371285
One of the key difficulties in using estimation-of-distribution algorithms is choosing the population sizes appropriately: Too small values lead to genetic drift, which can cause enormous difficulties. In the regime with no genetic drift, however, often the runtime is roughly proportional to the population size, which renders large population sizes inefficient. Based on a recent quantitative analysis which population sizes lead to genetic drift, we propose a parameter-less version of the compact genetic algorithm that automatically finds a suitable population size without spending too much time in situations unfavorable due to genetic drift. We prove an easy mathematical runtime guarantee for this algorithm and conduct an extensive experimental analysis on four classic benchmark problems. The former shows that under a natural assumption, our algorithm has a performance similar to the one obtainable from the best population size. The latter confirms that missing the right population size can be highly detrimental and shows that our algorithm as well as a previously proposed parameter-less one based on parallel runs avoids such pitfalls. Comparing the two approaches, ours profits from its ability to abort runs which are likely to be stuck in a genetic drift situation.
Most existing multiobjective evolutionary algorithms (MOEAs) assume the existence of Pareto-optimal solutions/Pareto-optimal objective vectors in a neighborhood of an obtained Pareto-optimal set (PS)/Pareto-optimal fr...
详细信息
Most existing multiobjective evolutionary algorithms (MOEAs) assume the existence of Pareto-optimal solutions/Pareto-optimal objective vectors in a neighborhood of an obtained Pareto-optimal set (PS)/Pareto-optimal front (PF). Obviously, this assumption does not work well on the multiobjective problem (MOP) whose true PF and true PS are in the form of multiple segments-truly disconnected MOP (TYD-MOP). Moreover, these MOEAs commonly involve more than three control parameters;and some of them even involve nine control parameters. The stabilities of their performance against parameter settings are generally unknown. In this paper, we propose a MOEA, namely multiobjective density driven evolutionary algorithm (MODdEA), which can handle TYD-MOP. MODdEA stores all evaluated solutions by a binary space partitioning (BSP) tree. Benefiting from the BSP scheme, a fast solution density estimation by the archive is naturally obtained. MODdEA uses this estimated density together with the nondominated rank to probabilistically select mating individuals, which relaxes the neighborhood assumption on PF in a parameter-less manner. Moreover, two genetic operators, extended arithmetic crossover and diversified mutation, are proposed to enhance the explorative search ability of the algorithm. MODdEA is examined on two test problem sets. The first test set consists of six TYD-MOPs;the second test set consists of 17 benchmark MOPs which are commonly examined by the existing MOEAs. Comparing to 14 test MOEAs, MODdEA has superior performance on TYD-MOP and is competitive on MOP whose true PF and PS are one single connected segment.
暂无评论