From recent research on combinatorial optimization of the knapsack problem, quantum-inspired evolutionary algorithm (QEA) was proved to be better than conventional genetic algorithms. To improve the performance of the QEA, this paper proposes research issues on QEA such as a termination criterion, a Q-gate, and a two-phase scheme, for a class of numerical and combinatorial optimization problems. A new termination criterion is proposed which gives a clearer meaning on the convergence of Q-bit individuals. A novel variation operator H/sub /spl epsi// gate, which is a modified version of the rotation gate, is proposed along with a two-phase QEA scheme based on the analysis of the effect of changing the initial conditions of Q-bits of the Q-bit individual in the first phase. To demonstrate the effectiveness and applicability of the updated QEA, several experiments are carried out on a class of numerical and combinatorial optimization problems. The results show that the updated QEA makes QEA more powerful than the previous QEA in terms of convergence speed, fitness, and robustness.
From recent research on combinatorial optimization of the knapsack problem, quantum-inspired evolutionary algorithm (QEA) was proved to be better than conventional genetic algorithms. To improve the performance of the QEA, this paper proposes research issues on QEA such as a termination criterion, a Q-gate, and a two-phase scheme, for a class of numerical and combinatorial optimization problems. A new termination criterion is proposed which gives a clearer meaning on the convergence of Q-bit individuals. A novel variation operator H/sub /spl epsi// gate, which is a modified version of the rotation gate, is proposed along with a two-phase QEA scheme based on the analysis of the effect of changing the initial conditions of Q-bits of the Q-bit individual in the first phase. To demonstrate the effectiveness and applicability of the updated QEA, several experiments are carried out on a class of numerical and combinatorial optimization problems. The results show that the updated QEA makes QEA more powerful than the previous QEA in terms of convergence speed, fitness, and robustness.
This paper proposes a novel evolutionary algorithm inspired by quantum computing, called a quantum-inspired evolutionary algorithm (QEA), which is based on the concept and principles of quantum computing, such as a quantum bit and superposition of states. Like other evolutionary algorithms, QEA is also characterized by the representation of the individual, evaluation function, and population dynamics. However, instead of binary, numeric, or symbolic representation, QEA uses a Q-bit, defined as the smallest unit of information, for the probabilistic representation and a Q-bit individual as a string of Q-bits. A Q-gate is introduced as a variation operator to drive the individuals toward better solutions. To demonstrate its effectiveness and applicability, experiments were carried out on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that QEA performs well, even with a small population, without premature convergence as compared to the conventional genetic algorithm.
In this paper, some guidelines for setting the parameters of quantum-inspired evolutionary algorithm (QEA) are presented. QEA is based on the concept and principles of quantum computing, such as a quantum bit and superposition of states. However, QEA is not a quantum algorithm, but a novel evolutionary algorithm. Like other evolutionary algorithms, QEA is also characterized by the representation of the individual, the evaluation function, and the population dynamics. From recent research on the knapsack problem, the results of QEA are better than those of CGA (conventional GA). Although the performance of QEA is excellent, there is relatively little or no research on the effects of different settings for its parameters. This paper describes some guidelines for setting these parameters. The guidelines are drawn up based on extensive experiments carried out for a class of combinatorial and numerical optimization problems. Through the guidelines, the performance of QEA can be maximized.
In this paper, we propose a novel quantum-inspired evolutionary algorithm, called NQEA, for solving combinatorial optimization problems. NQEA uses a new Q-bit update operator to increase the balance between the exploration and exploitation of the search space. In the operator, first, the Q-bits of each individual in the population are updated based on the personal best measurement of that individual and the best measurement of current generation. Then, a restriction is applied to each Q-bit to prevent the premature convergence of its values. The results of experiments on the 0-1 knapsack and NK-landscapes problems show that NQEA performs better than a classical genetic algorithm, CGA, and two quantum-inspired evolutionary algorithms, QEA and vQEA, in terms of convergence speed and accuracy.
Quantum-inspired evolutionary algorithms (QIEAs), as a subset of evolutionary computation, are based on the principles of quantum computing such as quantum bits and quantum superposition. In this paper, we propose a multi-start quantum-inspired evolutionary algorithm, called MSQIEA. To improve the performance of the algorithm, a multi-measurement operator and a new strategy for updating the rotation angle is proposed. When Q-bit individuals start to converge to their final states, the best solution is stored and all Q-bits in each Q-bit individual are reinitialized. We compare the effectiveness of MSQIEA with a popular quantum-inspired evolutionary algorithm, called QEA, for solving 0-1 knapsack problem. The experimental results show that MSQIEA outperforms QEA and finds a solution with higher profit.
Quantum-Inspired Evolutionary Algorithm (QEA) has been shown to be better performing than classical Genetic Algorithm based evolutionary techniques for combinatorial optimization problems like 0/1 knapsack problem. QEA uses quantum computing-inspired representation of solution called Q-bit individual consisting of Q-bits. The probability amplitudes of the Q-bits are changed by application of Q-gate operator, which is classical analogous of quantum rotation operator. The Q-gate operator is the only variation operator used in QEA, which along with some problem specific heuristic provides exploitation of the properties of the best solutions. In this paper, we analyzed the characteristics of the QEA for 0/1 knapsack problem and showed that a probability in the range 0.3 to 0.4 for the application of the Q-gate variation operator has the greatest likelihood of making a good balance between exploration and exploitation. Experimental results agree with the analytical finding.
It was indicated from the recent research that Quantum Genetic Algorithm(QGA) outperformed conventional genetic algorithm in its lower running time and ability of finding better solution when it solved a class of numerical and knapsack of combinatorial optimization problems.However,with qutbit of quantum individual interfering,parameter γ of the termination criterion is difficult to determine.The rotate gate which can promote the population is difficult to change its state of qutbit,and this phenomenon often induces premature.To improve the performance of the QGA,a controllable rotate gate and a new termination criterion are proposed in this paper.The controllable rotation gate can induce the convergence of qutbit not only to either 0 or 1,but also to either e or 1-e,and make the proposed algorithm to escape the local optimum.Based on gathering factor and qutbit convergence factor,a new termination criterion is proposed.The qutbit decreases the impact on parameter γ,and the new terminate criterion can efficiently control the relation of better solution and its running time.In addition,the Simplex method is introduced as a local searching scheme,which greatly improves the performance of algorithm.At last,the global convergence of the proposed algorithm is proved in theory,and comparable numerical experiments show that the proposed algorithm is more powerful than the compared algorithm in solution quality and speed.