Abstract
Population diversity is very important in giving the algorithm the power to explore the search space and not get trapped in local optima. In this respect, using a probabilistic representation for the quantum individuals, the Quantum-inspired Evolutionary Algorithms (QiEA) claim higher diversity in the population. Here, considering this important feature of QiEA, we propose different structures to offer better interaction between the q-individuals and propose new operators to preserve the diversity in the population and thus improve the performance of the QiEA. The effect of the structured population is investigated on the performance of the algorithm. Additionally, two operators are proposed in this paper. Being called the Diversity Preserving QiEA the first operator finds the converged similar q-individuals around a local optimum and while keeping the best q-individuals, by reinitializing the inferior ones pushes them out of the basin of attraction of the local optimum, so helping the algorithm to search other regions in the search space. The other operator is a reinitialization operator which by reinitializing the whole population helps it escape from the local optima it is trapped in. By studying the effect of the parameters of the proposed operators on their performance we show how the proposed operators improve the performance of QiEA. Experiments are performed on Knapsack, Trap and fourteen numerical objective functions and the results show better performance for the proposed algorithm than the original version of QiEA.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Alba E, Dorronsoro B (2005) The exploration/exploitation tradeoff in dynamic cellular genetic algorithms. IEEE Trans Evol Comput 9(2):126–142
Alba E, Tomassini M (2002) Parallelism and evolutionary algorithms. IEEE Trans Evol Comput 6(5):443–462
Arabas J, Michalewicz Z, Mulawka J (1994) Gavaps-a genetic algorithm with varying population size. In: IEEE world congress on computational intelligence, Proceedings of the 1st IEEE conference on evolutionary computation, vol 1, pp 73–78
Bryden K, Ashlock D, Corns S, Willson S (2006) Graph-based evolutionary algorithms. IEEE Trans Evol Comput 10(5):550–567
Cant-Paz E (2000) Efficient and accurate parallel genetic algorithms, 1st, edn. Kluwer, Hingham, MA
Chang PC, Huang WH, Ting CJ (2010) Dynamic diversity control in genetic algorithm for mining unsearched solution space in tsp problems. Expert Syst Appl 37(3):1863–1878. http://www.sciencedirect.com/science/article/pii/S0957417409006812
Dick G (2003) The spatially-dispersed genetic algorithm: an explicit spatial population structure for gas. In: The 2003 congress on evolutionary computation 2003, CEC ’03, vol 4, pp 2455–2461
dos Santos Nicolau A, Schirru R, de Moura Meneses AA (2011) Quantum evolutionary algorithm applied to transient identification of a nuclear power plant. Prog Nucl Energy 53(1):86–91
Duan HB (2010) A hybrid artificial bee colony optimization and quantum evolutionary algorithm for continuous optimization problems. Int J Neural Syst 20(1):39–50
Gu J, Gu M, Cao C, Gu X (2010) A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem. Comput Oper Res 37(5):927–937
Han CW, Park JI (2006) Population structure of heuristic search algorithm based on adaptive partitioning. Adv Appl Artif Intell, vol 4031, Lecture notes in Computer Science. Springer, Berlin, pp 238–243
Han H, Kim H (2004) Quantum-inspired evolutionary algorithms with a new termination criterion, h\(_\epsilon\) gate, and two-phase scheme. IEEE Trans Evol Comput 8(2):156–169
Han KH, Kim JH (2002) Quantum-inspired evolutionary algorithm for a class of combinatorial optimization. IEEE Trans Evol Comput 6(6):580–593
Han KH, Kim JH (2003) On setting the parameters of quantum-inspired evolutionary algorithm for practical application. In: The 2003 congress on evolutionary computation, 2003. CEC ’03, vol 1, pp 178–194
Han KH, Park KH, Lee CH, Kim JH (2001) Parallel quantum-inspired genetic algorithm for combinatorial optimization problem. In: Proceedings of the 2001 congress on evolutionary computation, vol 2, pp 1422–1429
Haupt R (2000) Optimum population size and mutation rate for a simple real genetic algorithm that optimizes array factors. In: Antennas and propagation society international symposium, 2000. IEEE, vol 2, pp 1034–1037
Hong Y, Ren Q, Zeng J (2005) Adaptive population size for univariate marginal distribution algorithm. In: The 2005 IEEE congress on evolutionary computation, 2005, vol 2, pp 1396–1402
Jang JS, Han KH, Kim JH (2003) Genetic and evolutionary computation GECCO 2003, vol 2724, Lecture notes in Computer Science, Springer, Berlin
Jang JS, Han KH, Kim JH (2004) Face detection using quantum-inspired evolutionary algorithm. In: Congress on evolutionary computation, 2004. CEC2004, vol 2, pp 2100–2106
Kaveh A, Shahrouzi M (2006) A hybrid ant strategy and genetic algorithm to tune the population size for efficient structural optimization. Emerald J Eng Comput 24:237–254
Kennedy J, Mendes R (2002) Population structure and particle swarm performance. In: Proceedings of the 2002 congress on evolutionary computation, 2002. CEC ’02, vol 2, pp 1671–1676
Khor E, Tan K, Wang M, Lee T (2000) Evolutionary algorithm with dynamic population size for multi-objective optimization. In: Industrial Electronics Society, 2000. IECON 2000. 26th Annual Confjerence of the IEEE, vol 4, pp 2768–2773
Koumousis V, Katsaras C (2006) A saw-tooth genetic algorithm combining the effects of variable population size and reinitialization to enhance performance. IEEE Trans Evol Comput 10(1):19–28
Koumousis VK, Katsaras CP (2002) The effect of oscillating population size and re-initialization on the performance of genetic algorithms. In: Proceedings of the 3rd international conference on engineering computational technology. ICECT’03Civil-Comp Press, Edinburgh, pp 185–186
Li D, Wang L (2002) A study on the optimal population size of genetic algorithm. In: Proceedings of the 4th world congress on intelligent control and automation 2002, vol 4, pp 3019–3021
Li Y, Zhang Y, Zhao R, Jiao L (2004) The immune quantum-inspired evolutionary algorithm. In: IEEE international conference on systems, man and cybernetics, 2004, vol 4, pp 3301–3305
Li Z, Xu B, Yang L, Chen J, Li K (2009) Quantum evolutionary algorithm for multi-robot coalition formation. In: Proceedings of the 1st ACM/SIGEVO summit on genetic and evolutionary computation. ACM, New York, NY, pp 295–302
Lu Q, Shen G, Yu R (2003) A chaotic approach to maintain the population diversity of genetic algorithm in network training. Comput Biol Chem 27(3):363–371
Mallipeddi R, Suganthan P (2008) Empirical study on the effect of population size on differential evolution algorithm. In: IEEE congress on evolutionary computation, 2008 CEC 2008, IEEE world congress on computational intelligence, pp 3663–3670
Park S, Kim E, Cho BJ (2003) Genetic algorithm-based video segmentation with adaptive population size. In: Michaelis B, Krell G (eds) Pattern Recognition, vol 2781, Lecture notes in Computer Science. Springer, Berlin, pp 426–433
Qin C, Zheng J, Lai J (2007) A multiagent quantum evolutionary algorithm for global numerical optimization. Life System Modeling and Simulation, vol 4689, Lecture notes in Computer Science. Springer, Berlin, pp 380–389
Sekaj I, Oravec, M (2009) Selected population characteristics of fine-grained parallel genetic algorithms with re-initialization. In: Proceedings of the 1st ACM/SIGEVO summit on genetic and evolutionary computation, GEC ’09, ACM, pp 945–948
Sekaj I, Perkacz J (2007) Some aspects of parallel genetic algorithms with population re-initialization. In: IEEE congress on evolutionary computation, 2007, CEC 2007, pp 1333–1338
Shi X, Wan L, Lee H, Yang X, Wang L, Liang Y (2003) An improved genetic algorithm with variable population-size and a pso-ga based hybrid evolutionary algorithm. In: 2003 International conference on machine learning and cybernetics, vol 3, pp 1735–1740
Shimodaira H (1997) Dcga: a diversity control oriented genetic algorithm. In: Proceedings 9th IEEE international conference on tools with artificial intelligence, 1997, pp 367–374
Shimodaira H (2001) Methods for reinitializing the population to improve the performance of a diversity-control-oriented genetic algorithm. IEICE Trans Inf Syst E84–D(12):1745–1755
Tayarani M, Akbarzadeh T M, (2008) A cellular structure and diversity preserving operator in quantum evolutionary algorithms. In: IEEE congress on evolutionary computation, 2008. CEC 2008, IEEE world congress on computational intelligence, pp 2665–2670
Tayarani-N MH, Akbarzadeh-T MR (2008) A sinusoid size ring structure quantum evolutionary algorithm. In: 2008 IEEE conference on cybernetics and intelligent systems, pp 1165–1170
Tsoy Y (2003) The influence of population size and search time limit on genetic algorithm. In: Proceedings KORUS 2003, The 7th Korea-Russia international symposium on science and technology, 2003, vol 3, pp 181–187
Vlachogiannis J, Lee K (2008) Quantum-inspired evolutionary algorithm for real and reactive power dispatch. IEEE Trans Power Syst 23(4):1627–1636
Wang Y, Feng XY, Huang YX, Pu DB, Zhou WG, Liang YC, Zhou CG (2007) A novel quantum swarm evolutionary algorithm and its applications. Neurocomputing 70(4):633–640
Xiao J, Xu J, Chen Z, Zhang K, Pan L (2009) A hybrid quantum chaotic swarm evolutionary algorithm for dna encoding. Comput Math Appl 57(11):1949–1958
Yang S, Wang M, Jiao L (2004) A novel quantum evolutionary algorithm and its application. In: Congress on evolutionary computation, 2004, CEC2004, vol 1, pp 820–826
Yong H (2007) Optimal population size for partheno-genetic algorithm. In: Chinese control conference, 2007. CCC 2007, pp 105–106
You X, Liu S, Shuai D (2006) On parallel immune quantum evolutionary algorithm based on learning mechanism and its convergence. Adv Nat Comput, vol 4221, Lecture notes in Computer Science. Springer, Berlin, pp 903–912
Yukiko Y, Nobue A (1994) A diploid genetic algorithm for preserving population diversity pseudo-meiosis ga. In: Davidor Y, Schwefel HP, Mnner R (eds) Parallel problem solving from nature PPSN III, vol 866, Lecture notes in Computer Science. Springer, Berlin, pp 36–45
Zhong W, Liu J, Xue M, Jiao L (2004) A multiagent genetic algorithm for global numerical optimization. IEEE Trans Syst Man Cybern B Cybern 34(2):1128–1141
Zhong W, Liu J, Xue M, Jiao L (2004) A multiagent genetic algorithm for global numerical optimization. IEEE Trans Syst Man Cybern B Cybern 34(2):1128–1141. doi:10.1109/TSMCB.2003.821456
Zhou A, Jin Y, Zhang Q, Sendhoff B, Tsang, E (2007) Prediction-based population re-initialization for evolutionary dynamic multi-objective optimization. In: Proceedings of the 4th international conference on evolutionary multi-criterion optimization, EMO’07, pp 832–846. Springer-Verlag, Berlin. http://dl.acm.org/citation.cfm?id=1762545.1762615
Zhu K (2003) A diversity-controlling adaptive genetic algorithm for the vehicle routing problem with time windows. In: Proceedings 15th IEEE international conference on tools with artificial intelligence, 2003, pp 176–183
Author information
Authors and Affiliations
Corresponding author
Appendix
Appendix
In this section we describe the benchmark problems we have used in this paper.
1.1 Trap problem
The Trap problem is defined as,
where \(N\) is the number of traps and equals the size of the problem divided by 5. A Trap is defined as,
where the function “ones” returns the number of ones in the binary string \(x\). The Trap problem has a local optimum at \((0,0,0,0,0)\) and a global optimum at \((1,1,1,1,1)\).
1.2 Knapsack problem
The Knapsack problem is a well-known combinatorial optimization problem which belongs to the class of NP-Hard problems. The Knapsack problem can be described as selecting a set of items \(x_i\), \(i=1,2,\ldots ,m\) with profits \(p_i\), and weights \(w_i\) for a knapsack with capacity \(C\). Given a set of \(m\) items and a knapsack with capacity \(C\), select the subset of the items to maximize the profit function \(f(x)\),
such that,
In this paper we consider
where \({\rm R (.,.)}\) is a uniform random number generator, \(v=10\) and the knapsack capacity is determined as,
Two types of QiEA methods are used in this paper to test our proposed algorithms [13]: the penalty function and the repair method.
In the QiEA based on penalty functions, a binary of the length \(m\) represents a chromosome \(x\) which is a solution to the problem. The profit \(f(x)\) of each string is determined as
where Pen\((x)\) is a penalty function. There are different ways of assigning the penalty function [13]. Here we use two types of penalties: the logarithmic and the liner penalty,
where \(\rho\) is \(\max _{i=1}^m\{p_i/w_i\}\).
In QiEA based on repair methods, the profit \(f(x)\) of each string is determined as,
where \(x'\) is a repaired vector of the original vector \(x\). The only difference between the two types of the repairs is the way the items are removed from the knapsack:
- \(\hbox {Rep}_1\) :
-
(random repair): In this method the elements are selected randomly and then removed from the knapsack.
- \(\hbox {Rep}_2\) :
-
(greedy repair): The items in the knapsack are sorted in a decreasing order based on their profit to weight ratio. The selection procedure then chooses the last item for deletion.
1.3 Numerical functions
Global numeric optimization problems arise in many fields of science, engineering, and business [48]. Here we use 14 benchmark maximization functions for testing our proposed algorithm. The \(f_1{-}f_8\) are multimodal functions where the number of local optima increases with the problem dimension. For example \(f_1\) has about \(6^n\) local optima in \([-500,500]^n\) and \(f_2\) has about \(10^n\) local optima in the search space of \([-5.12,5.12]^n\).
Generalized Schwefel’s Function 2.26:
Generalized Rastrigin’s Function:
Ackley’s Function:
Generalized Griewank Function:
Generalized Penalized Function 1:
Generalized Penalized Function 2:
Michalewicz Function:
Goldberg & Richardson Function:
Sphere Model:
Schwefel’s Function 2.22:
Schwefel’s Function 2.21:
Dejong Function 4:
Rosenbrock Function:
Kennedy multimodal function generator:
Where \(U\) is the search space and n is the problem dimension. These functions have several local minima and one global minimum. Since they are used for maximization process, we use it with a negative sign change \(f(x)\) for fitness function.
Rights and permissions
About this article
Cite this article
Tayarani-N, M.H., Akbarzadeh-T, M.R. Improvement of the performance of the Quantum-inspired Evolutionary Algorithms: structures, population, operators. Evol. Intel. 7, 219–239 (2014). https://doi.org/10.1007/s12065-014-0120-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12065-014-0120-8