When Evolutionary algorithms are used for solving constraint optimization problems, how to deal with the relationship between the feasible and infeasible parents directly influences the quality of the final results. The ratio of feasible/infeasible parents in a population is first investigated. Through experimental studies on bench-mark and hypothetical problems, it is revealed that the solutions are very dependent on how the ratio of feasible I infeasible parents balanced. Also, this is dependent on the problem itself - what may be an optimal approach for one problem may not be optimal for another. The upper and lower bounds of the number of feasible parents are given out.
To fully utilize the scope between the upper and lower bounds, an evolutionary algorithm using feasibility-based grouping is proposed. Feasible and infeasible individuals are divided into two groups: feasible group and infeasible group. The evaluation and ranking of these two groups are performed separately. Two parents selection methods: proportional parent selection strategy and parent selection strategy inspired by population ecology are proposed for parents production from the two groups. Objective function and bubble sort method are selected as the fitness function and ranking method for the feasible group. Three existing evolutionary algorithms, dynamic penalty method, annealing penalty method, and stochastic ranking method, are modified to evaluate and rank the infeasible group. The new method is tested using a (μ, λ)-ES on thirteen benchmark problems. The influence of (μ, λ) values on the results is also discussed.
수치 제한 조건 최적화 문제를 풀기 위해 진화 연산 알고리즘을 사용하는 경우, 실행 가능하거나 가능하지 않은 부모들의 관계를 어떻게 다루는가는 최종 결과의 질에 직접적으로 영향을 끼친다. 먼저, 한 세대에서 실행 가능/불가능한 부모들의 비율이 조사되었다. 진화 연산의 해는 실행가능/불가능한 부모들의 비율이 어떻게 조절되어있는가에 매우 의존한다는 것을 표준 문제와 가설 문제에 대한 실험적인 연구를 통해 입증하였다. 또한, 이것은 해당 문제에 따라 의존적인 결과를 보인다 (어떤 문제에 대해서는 최적의 접근 방법일 수 있으나, 다른 문제에 대해서는 아닐 수도 있다). 그리고, 실행 가능한 부모들의 상한, 하한 값들이 제시되었다.
상한/하한의 영역을 완전히 사용하기 위해서 실행 가능성 기반 그룹핑을 사용한 진화 연산 알고리즘이 제안되었다. 실행 가능하거나 가능하지 않은 개체들을 실행 가능 그룹과 실행 불가능 그룹으로 나누었다. 두 그룹에 대한 평가와 순위 매기기는 독립적으로 이루어진다. 부모를 선정하기 위한 방법으로 비례적 부모 선정법과 개체 생태학에 근거한 부모 선정법이 제안되었다. 실행 가능한 그룹에 대한 적합도 함수와 순위 매기기를 위해 목적 함수와 거품 정렬 방법이 선택되었다. 실행 불가능한 그룹에 대한 평가와 순위 매기기를 위해 기존의 dynamic penalty method, annealing penalty method, 그리고 stochastic ranking method를 수정하여 사용하였다. 제안된 새로운 방법을 13개의 표준 문제에 대해서 (μ, λ)-ES를 사용하여 검증하였다. 또한, (μ, λ) 값이 결과에 미치는 영향에 대해서 고찰하였다.
