×

A hybrid quantum-inspired immune algorithm for multiobjective optimization. (English) Zbl 1207.65078

Summary: This study suggests a novel quantum immune algorithm for finding Pareto-optimal solutions to multiobjective optimization problems based on quantum computing and immune system. In the proposed algorithm, there are distinct characteristics as follows.
First, the encoding method is based on Q-bit representation, and thus a chaos-based approach is suggested to initialize the population. Second, a new chaos-based rotation gate and Q-gates are presented to perform mutation and improve the quality of the population, respectively. Finally, especially, a new truncation algorithm with similar individuals (TASI) is utilized to preserve the diversity of the population.
Also, a new selection operator is proposed to create the new population based on TASI. Simulation results on six standard problems (ZDT6, CP, SP, VNT, OSY and KIT) show the proposed algorithm is able to find a much better spread of solutions and has better convergence near the true Pareto-optimal front compared to the vector immune algorithm (VIS) and the elitist non-dominated sorting genetic system (NSGA-II).

MSC:

65K05 Numerical mathematical programming methods
90C29 Multi-objective and goal programming
81P68 Quantum computation
68Q12 Quantum algorithms and complexity in the theory of computing

Software:

SPEA2
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Deb, K., Multi-Objective Optimization Using Evolutionary Algorithms (2001), John Wiley & Sons, Ltd: John Wiley & Sons, Ltd New York · Zbl 0970.90091
[2] Coello Coello, C. A.; Lamont, G. B.; Van Veldhuizen, D. A., Evolutionary Algorithms for Solving Multi-objective Problems (2008), Springer Science: Springer Science New York · Zbl 1130.90002
[3] de Castro, L. N.; Timmis, J., Artificial Immune System: A New Computational Intelligence Approach (2002), Springer-Verlag: Springer-Verlag Heidelberg · Zbl 1027.68108
[4] Hart, E.; Timmis, J., Application areas of AIS: the past, the present and the future, Appl. Soft Comput., 8, 1, 191-201 (2008)
[5] Coello, C. A.; Cruz Cortés, N., An approach to solve multiobjective optimization problems based on an artificial immune system, (Timmis, J.; Bentley, P. J., First International Conference on Artificial Immune Systems(ICARIS2002) (2002), University of Kent: University of Kent Canterbury, England), 212-221
[6] Luh, G. C.; Chueh, C. H.; Liu, W. W., MOIA: multi-objective immune algorithm, Eng. Optimiz., 35, 2, 143-164 (2003)
[7] Luh, G. C.; Chueh, C. H.; Liu, W. W., Multi-objective optimal design of truss structure with immune algorithm, Comput. Struct., 82, 829-844 (2004)
[8] Jiao, L.; Gong, M.; Shang, R., Clonal selection with immune dominance and energy based multiobjective optimization, (Proceedings of Third International Conference on Evolutionary Multi-Criterion Optimization, Guanajuato. Proceedings of Third International Conference on Evolutionary Multi-Criterion Optimization, Guanajuato, LNCS, Vol. 3410 (2005), Springer-Verlag: Springer-Verlag Mexico), 474-489 · Zbl 1109.68610
[9] Zhang, X.; Lu, B.; Gou, S.; Jiao, L., Immune multiobjective optimization algorithm for unsupervised feature selection, in Proceedings of Applications of Evolutionary Computing, Vol. 39 (2006), Springer: Springer Budapest, Hungary, LNCS
[10] Freschi, F.; Repetto, M., VIS: An artificial immune network for multi-objective optimization, Eng. Optimiz., 38, 8, 975-996 (2006)
[11] X.L. Wang, M. Mahfouf, ACSAMO: an adaptive multiobjective optimization algorithm using the clonal selection principle, in: Proceedings of Second European Symposium on Nature-inspired Smart Information Systems, Puerto de la Cruz, Tenerife, Spain, 2006.; X.L. Wang, M. Mahfouf, ACSAMO: an adaptive multiobjective optimization algorithm using the clonal selection principle, in: Proceedings of Second European Symposium on Nature-inspired Smart Information Systems, Puerto de la Cruz, Tenerife, Spain, 2006.
[12] Zhang, Z. H., Multiobjective optimization immune algorithm in dynamic environments and its application to greenhouse control, Appl. Soft Comput., 8, 959-971 (2008)
[13] Gao, J. Q.; Wang, L., WBMOAIS: A novel artificial immune system for multiobjective, Comput. Oper. Res., 37, 1, 50-61 (2010) · Zbl 1171.90518
[14] Shor, P. W., Algorithms for quantum computation: discrete logarithms and factoring.. Algorithms for quantum computation: discrete logarithms and factoring., Proceedings of 35th annual symposium foundations of computer science (1994), IEEE Press: IEEE Press Piscataway, NJ, pp.124-134
[15] Grover, L. K., Quantum mechanical searching, (Proceedings of 1999 congress on evolutionary computation (1999), IEEE Press: IEEE Press Piscataway, NJ), 2255-2261
[16] Han, K. H.; Kim, J. H., Quantum-inspired evolutionary algorithm for a class of combinatorial optimaization, IEEE Trans. Evol. Comput., 6, 6, 580-593 (2002)
[17] Han, K. H.; Kim, J. H., Quantum-inspired evolutionary algorithms with a new termination criterion, \(H_{ &z.epsiv; }\) gate, and two-phase scheme, IEEE Trans. Evol. Comput., 8, 2, 156-169 (2004)
[18] Kim, Y.; Kim, J. H.; Han, K. H., Quantum-inspired multiobjective evolutionary algorithm for multiobjective 0/1 knapsack problems, (Proceedings of 2006 IEEE Congress on Evolutionary Computation (2006), Vancouver, IEEE Press: Vancouver, IEEE Press Canada), 2601-2606
[19] Li, B. B.; Wang, L., A hybrid quantum-inspired genetic algorithm for multiobjective flow shop scheduling, IEEE Trans. Evol. Comput., 37, 3, 576-591 (2007)
[20] Li, P. C.; Li, S. Y., Learning algorithm and application of quantum BP neural networks based on universial quantum gates, J. Sys. Eng. Electron., 19, 1, 167-174 (2008) · Zbl 1219.68133
[21] Li, P. C.; Li, S. Y., Quantum ant colony algorithm for continuous space optimization, Chinese J. Control Theory Appl., 25, 2, 237-241 (2008)
[22] Aguirre, A. H.; Botello Rionda, S.; Coello, C. A., Handling constraints using multiobjective optimization concepts, Int. J. Numer. Meth. Eng., 59, 1989-2017 (2004) · Zbl 1060.74581
[23] Deb, K.; Pratap, A.; Agarwal, S., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., 6, 2, 182-197 (2002)
[24] J.R. Schott, Fault Tolerant Design Using Single and Multi-criteria Genetic Algorithms, Master’s Thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Boston, MA, 1995.; J.R. Schott, Fault Tolerant Design Using Single and Multi-criteria Genetic Algorithms, Master’s Thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Boston, MA, 1995.
[25] D.V. Veldhuizen, Multiobjective Evolutionary Algorithms: Classifications, Analyses and New Innovations, Phd Thesis, Air Force Institute of Technology, Dayton, OH, 1999.; D.V. Veldhuizen, Multiobjective Evolutionary Algorithms: Classifications, Analyses and New Innovations, Phd Thesis, Air Force Institute of Technology, Dayton, OH, 1999.
[26] Zitzler, E.; Deb, K.; Thiele, L., Comparison of multiobjective evolutionary algorithms: Empirical results, Evol. Comput., 8, 2, 125-148 (2000)
[27] Deb, K.; Thiele, L.; Laumanns, M.; Zitzler, E., Scalable test problems for evolutionary multiobjective optimization, (Abraham, A.; Jain, R.; Goldberg, R., Evolutionary Multiobjective Optimization: Theoretical Advances and Applications (2005), Springer), 105-145 · Zbl 1078.90567
[28] Viennet, R., Multicriteria optimization using a genetic algorithm for determining the Pareto set, Int. J. Sys. Sci., 27, 2, 255-260 (1996) · Zbl 0844.90079
[29] Osyczka, A.; Kundu, S., A new method to solve generalized multicriteria optimization problems using the simple genetic algorithm, Struct. Optimiz., 10, 94-99 (1995)
[30] Kita, H.; Yabumoto, Y.; Mori, N.; Nishikawa, Y., Multi-objective optimization by means of the thermodynamical genetic algorithm, (Voigt, H. M.; Ebeling, W., Parallel Problem Solving from Nature CPPSN IV (1996), Springer-Verlag: Springer-Verlag Berlin, LCNS), 504-512
[31] Coello Coello, C. A.; Toscano Pulido, G.; Salazar Lechuga, M., Handling multiple objectives with particle swarm optimization, IEEE Trans. Evol. Comput., 8, 256-279 (2004)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.