A reference set based many-objective co-evolutionary algorithm with an application to the knapsack problem
European Journal of Operational Research, cilt.300, sa.2, ss.405-417, 2022 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 300 Sayı: 2
- Basım Tarihi: 2022
- Doi Numarası: 10.1016/j.ejor.2021.10.033
- Dergi Adı: European Journal of Operational Research
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, International Bibliography of Social Sciences, ABI/INFORM, Applied Science & Technology Source, Business Source Elite, Business Source Premier, Computer & Applied Sciences, EconLit, INSPEC, Public Affairs Index, zbMATH, Civil Engineering Abstracts
- Sayfa Sayıları: ss.405-417
- Anahtar Kelimeler: Co-evolution, Combinatorial optimization, Evolutionary computations, Many-objective, Multiple objective programming
- Boğaziçi Üniversitesi Adresli: Evet
Özet
Despite the growing interest on many-objective evolutionary algorithms, studies on combinatorial problems are still rare. In this study, we choose many-objective knapsack problem (MaOKP) as the benchmark and target the challenges imposed by many-objectives in discrete search spaces by investigating several reference set handling approaches and combining several prominent evolutionary strategies in an innovative fashion. Our proposed algorithm uses elitist nondominated sorting and reference set based sorting, however reference points are mapped onto a fixed hyperplane obtained at the beginning of the algorithm. All evolutionary mechanisms are designed in a way to complement the reference set based sorting. Reference point guided path relinking is proposed as the recombination scheme for this purpose. Repair and local improvement procedures are also guided by reference points. Moreover, the reference set co-evolves simultaneously with the solution set, using both cooperative and competitive interactions to balance diversity and convergence, and adapts to the topology of the Pareto front in a self-adaptive parametric way. Numerical experiments display the success of the proposed algorithm compared to state-of-art approaches and yield the best results for MaOKP. The findings are inspiring and encouraging for the use of co-evolutionary reference set based techniques for combinatorial optimization.