Strength Pareto Evolutionary Algorithm Based on New Fitness Strategy for Multi Objective Knapsack Problem

Authors

  • Muna Shaker Salman Middle Technical University, Technical Institute- Suwaira , Iraq

DOI:

https://doi.org/10.29304/jqcm.2022.14.4.1096

Keywords:

Multi objective Optimization, Evolutionary Algorithms, EMO, SPEA2

Abstract

problems. Many different experiments have shown that the evolutionary algorithm Strength Pareto Evolutionary Algorithm 2 (SPEA2) outperforms other approaches, and this makes it an excellent candidate for inclusion in the final design. According to Strength, one of SPEA2's core concepts, the population is sorted into niches based on the Pareto Front idea. With regard to outcomes this technique has a flaw that is mitigated by adding a fitness density estimator. Weakness in Strength is addressed with an approach called Strength by objective, which aims to include solution who do not dominate or are dominated by others inside the process.  In this paper, the results will show a clear superiority of the proposed method comparing with the original method in solving the multi-objective Knapsack problem using three sizes of the Knapsack and the problem size of 750 items which is generated randomly. The comparison results between the proposed method and the other algorithms show outperformance of the Proposed algorithm using the dominance inductor showed the superiority of the proposed algorithm by a percentage of more than 1 %, Thanks to a highly diverse population and the inclusion of solutions that can be improved, the (SPEA2) algorithm's performance has been vastly enhanced by the Objective sorting mechanism

Downloads

Download data is not yet available.

References

[1]. Zitzler, Eckart, and Lothar Thiele. " Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach." IEEE transactions on Evolutionary Computation vol. 3, no.4,257-271,(1999), 10.1109/4235.797969.

[2]. Zitzler, Eckart, Kalyanmoy Deb, and Lothar Thiele. "Comparison of multiobjective evolutionary algorithms: Empirical results." Evolutionary computation vol.8,no.2 ,173-195, (2000), 10.1162/106365600568202‏.

[3]. Deb, Kalyanmoy, et al. "A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II." International conference on parallel problem solving from nature. Springer, Berlin, Heidelberg, 2000.

[4]. Deb, Kalyanmoy, et al. "A fast and elitist multiobjective genetic algorithm: NSGA-II." IEEE transactions on evolutionary computation vol.6,no.2 , 182-197, (2002), 10.1109/4235.996017.

[5]. Mansour, Imen Ben, Mathieu Basseur, and Frédéric Saubion. "A multi-population algorithm for multi-objective knapsack problem." Applied Soft Computing vol. 70,814-825,(2018), https://doi.org/10.1016/j.asoc.2018.06.024‏

[6]. Luo, Rong-juan, Shou-feng Ji, and Bao-lin Zhu. "A Pareto evolutionary algorithm based on incremental learning for a kind of multi-objective multidimensional knapsack problem." Computers & Industrial Engineering , vol. 135: 537-559, (2019),https://doi.org/10.1016/j.cie.2019.06.027

[7]. Osawa, R., Watanabe, S., Hiroyasu, T., & Hiwa, S. (2019, December). Performance Study of Double-Niched Evolutionary Algorithm on Multi-objective Knapsack Problems. In 2019 IEEE Symposium Series on Computational Intelligence (SSCI) (pp. 1793-1801). IEEE, 10.1109/SSCI44817.2019.9003130.‏

[8]. Zapotecas-Martínez, S., & Menchaca-Méndez, A. (2020, July). On the Performance of Generational and Steady-State MOEA/D in the Multi-Objective 0/1 Knapsack Problem. In 2020 IEEE Congress on Evolutionary Computation (CEC) (pp. 1-8). IEEE, 10.1109/CEC48606.2020.9185715.

[9]. Jiang, S., & Yang, S. (2017). A strength Pareto evolutionary algorithm based on reference direction for multiobjective and many-objective optimization. IEEE Transactions on Evolutionary Computation, 21(3), 329-346.

Downloads

Published

2022-12-02

How to Cite

Salman, M. S. (2022). Strength Pareto Evolutionary Algorithm Based on New Fitness Strategy for Multi Objective Knapsack Problem. Journal of Al-Qadisiyah for Computer Science and Mathematics, 14(4), Stat. Page 1–10. https://doi.org/10.29304/jqcm.2022.14.4.1096

Issue

Section

Statistic Articles