1. Bibliographic Information

1.1. Title

The title of the paper is "Quantum-Inspired Evolutionary Algorithm for a Class of Combinatorial Optimization." This title clearly indicates the central topic: a new type of evolutionary algorithm (EA) that draws inspiration from quantum computing principles, designed to solve combinatorial optimization problems.

1.2. Authors

The authors are:

• Kuk-Hyun Han

• Jong-Hwan Kim

  Kuk-Hyun Han was a Ph.D. student at the Korea Advanced Institute of Science and Technology (KAIST) in electrical engineering and computer science at the time of publication. His research interests included quantum-inspired evolutionary computation, internet-based personal robot systems, and intelligent control. Jong-Hwan Kim was a Professor in the Department of Electrical Engineering and Computer Science at KAIST. His research interests were in evolutionary multiagent robotic systems. He also served as an Associate Editor for the IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION and was involved with FIRA (The Federation of International Robot-soccer Association) and IROC (The International Robot Olympiad Committee).

1.3. Journal/Conference

The paper was published in the IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, vol. 6, no. 6. The IEEE Transactions on Evolutionary Computation is a highly reputable and influential journal in the field of evolutionary computation, indicating that the research underwent a rigorous peer-review process and is considered significant within the community.

1.4. Publication Year

The paper was published at (UTC): 2002-12-01T00:00:00.000Z, which corresponds to December 1, 2002.

1.5. Abstract

The paper introduces a novel evolutionary algorithm called the Quantum-Inspired Evolutionary Algorithm (QEA). This algorithm is based on quantum computing concepts such as the quantum bit (Q-bit) and superposition of states. Unlike conventional evolutionary algorithms that use binary, numeric, or symbolic representations for individuals, QEA employs a Q-bit for probabilistic representation. A Q-gate is introduced as a variation operator to guide individuals toward better solutions. Experimental results on the knapsack problem demonstrate that QEA performs effectively, even with a small population size, and avoids premature convergence compared to traditional genetic algorithms (GAs).

1.6. Original Source Link

The original source link provided is /files/papers/691e79048106199151d7ea11/paper.pdf. This link points to the PDF file of the paper, indicating it is an officially published work.

2. Executive Summary

2.1. Background & Motivation

The core problem the paper aims to solve is combinatorial optimization, which involves finding an optimal object from a finite set of objects. These problems are often NP-hard, meaning their computational complexity grows exponentially with the problem size, making them difficult to solve exactly in a reasonable amount of time for large instances. Evolutionary Algorithms (EAs) are a class of metaheuristics widely used for such problems due to their robustness and ability to find good solutions without getting stuck in local optima.

The motivation behind this research stems from inherent challenges in existing EAs, particularly Genetic Algorithms (GAs):

1. Balancing Exploration and Exploitation: EAs need to effectively explore the search space to find diverse solutions (exploration) while also focusing on refining promising solutions (exploitation). Achieving a good balance is crucial for performance.

2. Premature Convergence: Traditional GAs can suffer from premature convergence, where the population quickly converges to a suboptimal solution, losing diversity and failing to explore other potentially better regions of the search space. This often occurs when population sizes are small.

3. Population Size Limitations: Many EAs require a sufficiently large population to maintain diversity and prevent premature convergence. This can be computationally expensive for complex problems.

   The paper's entry point and innovative idea is to draw inspiration from quantum computing concepts, specifically the quantum bit (qubit) and superposition of states, to address these limitations within a classical computational framework. The goal is to design an EA that can represent individuals more effectively, explore the search space with a smaller population, and maintain diversity to avoid premature convergence, ultimately finding global solutions faster.

2.2. Main Contributions / Findings

The paper's primary contributions are:

1. Introduction of the Quantum-Inspired Evolutionary Algorithm (QEA): A novel evolutionary algorithm that incorporates principles from quantum computing for classical computers.
2. Q-bit Representation: QEA introduces a new probabilistic representation called the Q-bit, which can represent a linear superposition of states (binary solutions). This allows a single Q-bit individual to implicitly hold information about multiple possible solutions simultaneously, enhancing population diversity even with a small number of individuals.
3. Q-gate as a Variation Operator: A Q-gate is defined as a variation operator that updates the Q-bit probabilities. Specifically, a rotation gate is used to drive the probabilities of Q-bits towards either '0' or '1' states based on the fitness of observed solutions, thereby guiding the search process.
4. Demonstrated Effectiveness on the Knapsack Problem: Through experiments on the knapsack problem, QEA is shown to:

   • Perform well even with a small population size (e.g., a single individual), which is a significant advantage over conventional GAs.

   • Avoid premature convergence, maintaining diversity and continuing to find better solutions over a longer period.

   • Achieve a faster convergence rate and higher profit amounts compared to conventional GAs.

   • Exhibit an inherent mechanism that balances exploration and exploitation, starting with a global search and automatically transitioning to a local search.

     These findings suggest that QEA offers a robust and efficient alternative for combinatorial optimization problems, particularly when computational resources or the need for rapid convergence are critical.

3. Prerequisite Knowledge & Related Work

This section lays the groundwork by explaining the fundamental concepts and previous research that are essential for understanding the Quantum-Inspired Evolutionary Algorithm (QEA).

3.1. Foundational Concepts

3.1.1. Evolutionary Algorithms (EAs) and Genetic Algorithms (GAs)

Evolutionary Algorithms (EAs) are a family of optimization algorithms inspired by biological evolution. They operate on a population of potential solutions (called individuals or chromosomes) to a given problem. These individuals evolve over successive generations through processes analogous to natural selection and genetic variation.

Key components of EAs include:

• Individual Representation: How a potential solution is encoded (e.g., binary strings, real-valued numbers, symbolic expressions).

• Population: A collection of individuals.

• Fitness Function (Evaluation Function): A function that quantifies the quality of each individual solution. Higher fitness means a better solution.

• Variation Operators: Mechanisms that introduce diversity into the population, such as crossover (combining parts of two parent individuals) and mutation (randomly altering an individual's characteristics).

• Selection: Choosing individuals from the current population to create the next generation, usually favoring those with higher fitness (survival of the fittest).

• Exploration vs. Exploitation: Exploration refers to the algorithm's ability to search diverse regions of the solution space to find new promising areas. Exploitation refers to its ability to refine existing good solutions. A good EA balances these two.

  Genetic Algorithms (GAs) are a specific type of EA, pioneered by John Holland, that typically use binary string representations and apply specific crossover and mutation operators.

3.1.2. Combinatorial Optimization Problems

These are problems where the goal is to find an optimal solution from a finite (but often very large) set of discrete choices. The knapsack problem is a classic example: given a set of items, each with a weight and a value (profit), determine the subset of items to include in a knapsack so that the total weight does not exceed a given limit and the total value is as large as possible. Solutions are typically binary (an item is either in or out).

3.1.3. Quantum Computing Basics

Quantum computing is a new paradigm of computation that uses principles of quantum mechanics (like superposition and entanglement) to perform calculations. The paper draws inspiration from a few key concepts:

• Quantum Bit (Qubit): The fundamental unit of information in quantum computing, analogous to a classical bit. A classical bit can only be in state '0' or '1'. A qubit, however, can be in a superposition of both '0' and '1' states simultaneously.
  • The state of a qubit is represented as a linear combination: $$| \Psi \rangle = \alpha | 0 \rangle + \beta | 1 \rangle$$ where $|0\rangle$ and $|1\rangle$ are basis states (representing classical '0' and '1'), and $\alpha$ and $\beta$ are complex numbers called probability amplitudes.
  • Probability Amplitudes: $|\alpha|^2$ gives the probability of measuring the qubit in the '0' state, and $|\beta|^2$ gives the probability of measuring it in the '1' state.
  • Normalization: The sum of probabilities must be 1: $$| \alpha | ^ { 2 } + | \beta | ^ { 2 } = 1$$
• Superposition of States: The ability of a qubit to exist in multiple states simultaneously. If a system has $m$ qubits, it can represent $2^m$ states concurrently. This is a key inspiration for QEA's probabilistic representation, allowing one Q-bit individual to implicitly represent many binary solutions.
• Quantum Gates: Operations that modify the state of qubits. Analogous to logic gates in classical computers, but they must be reversible and unitary operators. Examples include NOT gate, Controlled NOT gate, and rotation gate. The rotation gate is particularly relevant to QEA as it allows for controlled changes in the probability amplitudes.
• Measurement/State Collapse: In actual quantum computers, observing a qubit causes its superposition to collapse into a single classical state ('0' or '1') with a probability determined by its amplitudes. While QEA doesn't perform actual quantum measurement, it simulates this probabilistic collapse to generate classical solutions.

3.2. Previous Works

The paper contextualizes its work by referencing the historical development of EAs and the emergence of quantum computing:

• Foundational EAs:
  • Genetic Algorithms (GAs): Developed by Fraser [1], Bremermann [2], and Holland [3] starting in the 1950s-1970s. These form the primary baseline for comparison in the paper.
  • Evolutionary Programming (EP): Developed by L. J. Fogel [4].
  • Evolution Strategies (ES): Developed by Rechenberg [5] and Schwefel [6].
• Quantum Computing:
  • Theoretical proposals for quantum mechanical computers emerged in the early 1980s by Benioff [7] and formalized by Deutsch [8] in the late 1980s.
  • Significant breakthroughs include Shor's quantum factoring algorithm [9], [10] (early 1990s) and Grover's database search algorithm [11], [12], demonstrating the potential power of quantum computers over classical ones for specific tasks.
• Merging Evolutionary Computing and Quantum Computing (Late 1990s): The paper identifies two main branches:
  1. Generating new quantum algorithms: Using automatic programming techniques like genetic programming to discover quantum algorithms (e.g., Spector et al. [13]). This is not the focus of the current paper.
  2. Quantum-inspired evolutionary computing for classical computers: This is the field QEA contributes to. This approach borrows concepts from quantum mechanics (e.g., superposition, interference, coherence) to design new EAs that run on classical hardware. Narayanan and Moore [14], [15] explored including the concept of interference in crossover operators for GAs. Han and Kim's own earlier work also includes "Genetic Quantum Algorithm" [16] and "Parallel quantum-inspired genetic algorithm" [17].

3.3. Technological Evolution

The field of optimization has evolved from traditional calculus-based or enumerative methods to metaheuristics like EAs, which are more robust and applicable to a wider range of problems, especially those that are non-differentiable or high-dimensional. The advent of quantum computing has opened up possibilities for fundamentally new computational approaches. Quantum-inspired evolutionary computing represents a hybrid step, leveraging the conceptual advantages of quantum mechanics (like efficient representation of multiple states) to enhance existing classical algorithms without requiring actual quantum hardware. This allows for immediate practical application and performance improvements on current classical computers.

3.4. Differentiation Analysis

Compared to conventional Genetic Algorithms (GAs) and other evolutionary computation methods, QEA introduces several core differences and innovations:

• Probabilistic Representation (Q-bit):
  • Conventional GAs: Use fixed, deterministic representations (e.g., binary strings like 0110, real numbers, or symbolic expressions). Each individual represents one solution.
  • QEA: Uses Q-bits to probabilistically represent a superposition of states. A single Q-bit individual can implicitly encode information about $2^m$ binary solutions (where $m$ is the number of Q-bits). This is a key innovation.
• Population Diversity:
  • Conventional GAs: Maintain diversity by having a large population of distinct individuals. Premature convergence occurs when diversity is lost, often necessitating large population sizes.
  • QEA: The inherent superposition property of Q-bits allows a small population (even a single Q-bit individual) to maintain population diversity probabilistically. This helps avoid premature convergence and makes QEA more efficient in terms of population size.
• Variation Operator (Q-gate):
  • Conventional GAs: Rely on crossover (recombining parts of parents) and mutation (random bit flips) to introduce changes and explore the search space.
  • QEA: Introduces the Q-gate, specifically a rotation gate, as a variation operator. Instead of directly altering solution components, the Q-gate modifies the probability amplitudes of Q-bits. This steers the probabilistic representation towards better solutions without losing the ability to explore alternative paths initially.
• Balancing Exploration and Exploitation:

  • Conventional GAs: The balance is often managed by tuning crossover/mutation rates and population size, which can be difficult.

  • QEA: The probabilistic nature of Q-bits (initially uniform superposition) allows for broad exploration. As the algorithm progresses and better solutions are found, the Q-gates gradually converge the probabilities of Q-bits towards '0' or '1', implicitly shifting to exploitation. This balance is an inherent mechanism of the Q-bit evolution.

    In essence, QEA leverages the quantum-inspired probabilistic representation to achieve superior diversity management and a more dynamic balance between exploration and exploitation, leading to better performance with fewer individuals and reduced premature convergence compared to its classical GA counterparts.

4. Methodology

4.1. Principles

The core idea of the Quantum-Inspired Evolutionary Algorithm (QEA) is to apply concepts from quantum computing, specifically the quantum bit (qubit) and superposition of states, to the design of an evolutionary algorithm running on a classical computer. The theoretical basis or intuition behind this is that a probabilistic representation, akin to a qubit's superposition, can allow an individual to simultaneously represent a multitude of possible solutions. This implicitly maintains population diversity and provides a mechanism for balancing exploration (searching broadly) and exploitation (focusing on promising areas) during the optimization process. By using a Q-gate to evolve these probabilistic representations, QEA aims to drive the search efficiently towards optimal solutions.

4.2. Core Methodology In-depth (Layer by Layer)

QEA operates on a population of Q-bit individuals rather than conventional binary, numeric, or symbolic individuals. The overall structure of QEA is depicted in Figure 1, which integrates a loop for generational evolution with steps for initialization, observation, evaluation, and update.

The following figure (Figure 1 from the original paper) shows the overall structure of QEA:

Figure 1. Overall structure of QEA.

4.2.1. Basics of Quantum-Inspired Concepts

4.2.1.1. Q-bit Representation

The Q-bit is the fundamental unit of information in QEA, inspired by the quantum mechanical qubit.

Definition 1: Q-bit A Q-bit is defined as a pair of numbers $(\alpha, \beta)$, represented as a column vector: $$\left[ { \begin{array} { l } { \alpha } \\ { \beta } \end{array} } \right]$$ where $\alpha$ and $\beta$ are probability amplitudes. These amplitudes must satisfy the normalization condition: $$| \alpha | ^ { 2 } + | \beta | ^ { 2 } = 1$$ Here, $|\alpha|^2$ represents the probability that the Q-bit will be measured in the '0' state, and $|\beta|^2$ represents the probability that it will be measured in the '1' state. This means a Q-bit can be in the '0' state, the '1' state, or a linear superposition of both.

Definition 2: Q-bit Individual A Q-bit individual is defined as a string of $m$ Q-bits: $$[ \begin{array} { c } { \alpha _ { 1 } } \\ { \beta _ { 1 } } \end{array} | \begin{array} { c } { \alpha _ { 2 } } \\ { \beta _ { 2 } } \end{array} | \begin{array} { c } { \cdots } \\ { \cdots } \end{array} | \begin{array} { c } { \alpha _ { m } } \\ { \beta _ { m } } \end{array} ]$$ where for each Q-bit $i$ (from 1 to $m$), the normalization condition $| \alpha _ { i } | ^ { 2 } + | \beta _ { i } | ^ { 2 } = 1$ holds.

The key advantage of this representation is its ability to represent a linear superposition of states. For example, a three-Q-bit system with each Q-bit in a superposition (e.g., $\left[ \frac { 1 } { \sqrt { 2 } } | \frac { 1 } { \sqrt { 2 } } \right]$, which means equal probability for 0 and 1) can implicitly contain information about $2^3 = 8$ different binary states (e.g., |000⟩, |001⟩, ..., |111⟩) simultaneously, each with a specific probability. This provides a rich population diversity even with a single Q-bit individual.

4.2.1.2. Q-gate as a Variation Operator

A Q-gate is introduced as the primary variation operator in QEA, responsible for updating the Q-bit individuals.

Definition 3: Q-gate A Q-gate is a variation operator that modifies a Q-bit such that the updated Q-bit $(\alpha', \beta')$ still satisfies the normalization condition: $| \alpha ^ { \prime } | ^ { 2 } + | \beta ^ { \prime } | ^ { 2 } = 1$.

In QEA, a rotation gate is specifically used as the Q-gate. This gate rotates the Q-bit's state vector on the complex plane. For a single Q-bit $(\alpha_i, \beta_i)$, the update rule using a rotation gate $U(\Delta\theta_i)$ is: $$\left[ \begin{array} { c } { \alpha _ { i } ^ { \prime } } \\ { \beta _ { i } ^ { \prime } } \end{array} \right] = \left[ \begin{array} { c c } { \cos ( \Delta \theta _ { i } ) } & { - \sin ( \Delta \theta _ { i } ) } \\ { \sin ( \Delta \theta _ { i } ) } & { \cos ( \Delta \theta _ { i } ) } \end{array} \right] \left[ \begin{array} { c } { \alpha _ { i } } \\ { \beta _ { i } } \end{array} \right]$$ Here, $\alpha_i$ and $\beta_i$ are the current probability amplitudes of the $i$-th Q-bit, $\alpha_i'$ and $\beta_i'$ are the updated amplitudes, and $\Delta\theta_i$ is a rotation angle. The sign and magnitude of $\Delta\theta_i$ determine how the probabilities shift, driving the Q-bit towards either the '0' or '1' state. Figure 2 illustrates this rotation.

The following figure (Figure 2 from the original paper) depicts the polar plot of the rotation gate for Q-bit individuals:

Figure 2. Polar plot of the rotation gate for Q-bit individuals.

4.2.2. QEA Procedure Steps

QEA maintains a population of Q-bit individuals, denoted as $Q(t) = \{ \mathbf{q}_1^t, \mathbf{q}_2^t, \ldots, \mathbf{q}_n^t \}$ at generation $t$, where $n$ is the population size and $\mathbf{q}_j^t$ is a Q-bit individual. The algorithm proceeds as follows:

1. Initialize Q(t) (Step i): At the initial generation ($t=0$), the probability amplitudes $\alpha_{ji}^0$ and $\beta_{ji}^0$ for all $i$-th Q-bits in all $j$-th Q-bit individuals $\mathbf{q}_j^0$ are set to $1/\sqrt{2}$. This means for every Q-bit, $|\alpha_{ji}^0|^2 = (1/\sqrt{2})^2 = 1/2$ and $|\beta_{ji}^0|^2 = (1/\sqrt{2})^2 = 1/2$. This configuration signifies that each Q-bit individual initially represents a linear superposition of all $2^m$ possible binary states with equal probability. Mathematically, for a Q-bit individual $\mathbf{q}_j^0$: $$\left| \Psi _ { \mathbf { q } _ { j } ^ { 0 } } \right. = \sum _ { k = 1 } ^ { 2 ^ { m } } { \frac { 1 } { \sqrt { 2 ^ { m } } } } \left| X _ { k } \right.$$ where $X_k$ is the $k$-th state represented by a binary string $(x_1 x_2 \cdots x_m)$.

2. Make P(t) by Observing States of Q(t) (Steps ii, v): For each Q-bit individual $\mathbf{q}_j^t$ in the population Q(t), a set of binary solutions $P(t) = \{ \mathbf{x}_1^t, \mathbf{x}_2^t, \ldots, \mathbf{x}_n^t \}$ is generated. This is done by observing each Q-bit probabilistically. For each $i$-th Q-bit $(\alpha_{ji}^t, \beta_{ji}^t)$, a random number $r$ between 0 and 1 is generated.

   • If $r < |\beta_{ji}^t|^2$, the $i$-th bit of the binary solution $\mathbf{x}_j^t$ is set to '1'.
   • Otherwise, it's set to '0'. This process simulates the collapse of a quantum state to a classical binary string, creating a concrete solution for evaluation.

3. Evaluate P(t) (Steps iii, vi): Each generated binary solution $\mathbf{x}_j^t$ in P(t) is evaluated using a fitness function specific to the optimization problem. This function assigns a fitness value (e.g., profit for knapsack) to each solution.

4. Store Best Solutions into B(t) (Steps iv, viii, ix): The best solutions found so far are stored in $B(t) = \{ \mathbf{b}_1^t, \mathbf{b}_2^t, \ldots, \mathbf{b}_n^t \}$.

   • Initially (Step iv), the best solutions from $P(0)$ are stored in $B(0)$.
   • In subsequent generations (Step viii), B(t) is updated by comparing solutions in B(t-1) and P(t).
   • An overall best solution $\mathbf{b}$ (the fittest solution found across all generations) is also maintained (Step ix).

5. Update Q(t) using Q-gates (Step vii): This is the core evolutionary step. The Q-bit individuals in Q(t) are updated by applying Q-gates. For each Q-bit $(\alpha_i, \beta_i)$ in a Q-bit individual $\mathbf{q}$, a rotation gate $U(\Delta\theta_i)$ is applied to update its amplitudes to $(\alpha_i', \beta_i')$. The rotation angle $\Delta\theta_i$ is crucial and is determined based on:

   • The corresponding bit $x_i$ from the currently observed binary solution $\mathbf{x}$.
   • The corresponding bit $b_i$ from the best solution $\mathbf{b}$ (or $\mathbf{b}_j^t$ from B(t)).
   • A comparison of their fitness values: $f(\mathbf{x})$ vs. $f(\mathbf{b})$. The specific values and signs of $\Delta\theta_i$ are determined by a lookup table (Table I, explained further in the knapsack example). The sign of $\Delta\theta_i$ is also influenced by the quadrant of the Q-bit's current state on the unit circle (Figure 2).

6. Migration (Step x): Definition 4: Migration in QEA Migration is a process to increase population diversity or prevent premature convergence by copying good solutions.

   • Global Migration: All Q-bit individuals in B(t) (or their corresponding Q-bit states) are replaced by the current overall best solution $\mathbf{b}$.
   • Local Migration: Some Q-bit individuals in B(t) are replaced by the best solution among a subset of them. This step is conditional, performed if a migration-condition (e.g., a specific generation period) is met.

The binary solutions in P(t) are discarded after evaluation and updating Q(t), as the next generation's $P(t+1)$ will be generated by observing the updated Q(t). This loop continues until a termination condition (e.g., maximum generations, satisfactory probability of the best solution) is met.

4.2.3. QEA for the Knapsack Problem

The application of QEA to the knapsack problem involves the basic QEA structure with an additional repair process to handle the capacity constraint.

The knapsack problem is defined as maximizing the total profit $f(\mathbf{x})$: $$f ( \mathbf { x } ) = \sum _ { i = 1 } ^ { m } p _ { i } x _ { i }$$ subject to the total weight constraint: $$\sum _ { i = 1 } ^ { m } w _ { i } x _ { i } \leq C$$ where:

• $\mathbf{x} = (x_1 \cdots x_m)$ is a binary vector representing the solution.

• $x_i \in \{0, 1\}$: 1 if item $i$ is selected, 0 otherwise.

• $p_i$: profit of item $i$.

• $w_i$: weight of item $i$.

• $C$: capacity of the knapsack.

  The procedure for QEA for the Knapsack Problem is similar to the general QEA, with two key additions:

Procedure QEA for the Knapsack Problem begin t ← 0 initialize Q(t) make P(t) by observing the states of Q(t) repair P(t) <-- Added step evaluate P(t) store the best solutions among P(t) into B(t) while (t < MAX_GEN) do begin $t ← t + 1$ make P(t) by observing the states of Q(t-1) repair P(t) <-- Added step evaluate P(t) update Q(t) store the best solutions among B(t-1) and P(t) into B(t) store the best solution b among B(t) $if (migration-period) then migrate b or b_j^t to B(t) globally or locally, respectively$ end end

4.2.3.1. Generating Binary Solutions (Make P(t))

For each Q-bit individual $\mathbf{q}$ and each Q-bit $i$ (with amplitudes $\alpha_i, \beta_i$), the corresponding binary bit $x_i$ is determined:

Procedure Make $\Psi(\mathbf{x})$ begin i ← 0 $while (i < m) do begin$ $i ← i + 1$ $if random[0, 1) < |β_i|^2 then x_i ← 1$ $else x_i ← 0$ end end where random[0, 1) generates a random number between 0 (inclusive) and 1 (exclusive).

4.2.3.2. Repair Process (Repair P(t))

Since the probabilistic observation can generate solutions that violate the knapsack's capacity constraint, a repair algorithm is employed to make infeasible solutions feasible.

Procedure Repair $\Psi(\mathbf{x})$ begin knapsack-overfilled ← false if\sum_{i=1}^{m} w_i x_i > Cthen knapsack-overfilled ← true while (knapsack-overfilled) do begin select an ith item from the knapsack (typically, remove items with low profit-to-weight ratio first, or randomly) $x_i ← 0$ (remove the item) if\sum_{i=1}^{m} w_i x_i \le Cthen knapsack-overfilled ← false end while (not knapsack-overfilled) do begin select a jth item from the knapsack (typically, add items with high profit-to-weight ratio first, or randomly) $x_j ← 1$ (try to add the item) if\sum_{i=1}^{m} w_i x_i > Cthen knapsack-overfilled ← true (if adding overflows, mark as overfilled) end $x_j ← 0$ (if adding item $j$ overfilled the knapsack, remove it back) end This repair process first removes items until the knapsack is no longer overfilled. Then, it attempts to add items back if space allows, always ensuring the capacity constraint is not violated. The specific selection of items to remove/add can vary (e.g., random or greedy).

4.2.3.3. Update Procedure (Update (q))

The Q-bits in Q-bit individual $\mathbf{q}$ are updated using the rotation gate based on the observed binary solution $\mathbf{x}$ and the best solution $\mathbf{b}$ found so far. The rotation angle $\Delta\theta_i$ for each $i$-th Q-bit is determined by a lookup table (Table I).

The following table (Table I from the original paper) shows the lookup table for $\Delta\theta_i$:

Table I. Lookup Table of $\Delta\theta_i$, Where $f(\cdot)$ is the profit, and $b_i$ and $x_i$ are the ith bits of the best solution $\mathbf{b}$ and the binary solution $\mathbf{x}$, respectively.

The Procedure Update (q) is as follows: Procedure Update (q) begin i ← 0 $while (i < m) do begin$ $i ← i + 1$ determine\Delta\theta_iwith the lookup table (Table I) obtain(\alpha_i', \beta_i')from the following: if (q is located in the first/third quadrant) (i.e., $\alpha_i \beta_i \ge 0$) then[\alpha_i' \beta_i']^T = U(\Delta\theta_i) [\alpha_i \beta_i]^T$ else (i.e., $\alpha_i \beta_i < 0$, second/fourth quadrant) then[\alpha_i' \beta_i']^T = U(-\Delta\theta_i) [\alpha_i \beta_i]^T$ end q ← q' end

The logic for determining $\Delta\theta_i$ (specifically $\theta_1$ to $\theta_8$) from Table I is intuitive:

• If the current solution bit $x_i$ matches the best solution bit $b_i$ (e.g., both 0 or both 1), and $f(\mathbf{x}) \ge f(\mathbf{b})$, then $\Delta\theta_i$ might be set to 0, indicating no change is needed for this bit.
• If $x_i$ is 0 and $b_i$ is 1, and $f(\mathbf{x}) < f(\mathbf{b})$ (meaning the current solution is worse, and this bit '0' is not contributing to a better solution), $\Delta\theta_i$ should be positive to increase the probability of '1' for the $i$-th bit.
• If $x_i$ is 1 and $b_i$ is 0, and $f(\mathbf{x}) < f(\mathbf{b})$, $\Delta\theta_i$ should be negative to increase the probability of '0' for the $i$-th bit. The quadrant check (first/third or second/fourth) ensures the rotation gate consistently drives the probability amplitudes in the desired direction (towards 0 or 1). For the knapsack problem, specific values used were $\theta_3 = 0.01\pi$, $\theta_5 = -0.01\pi$, and the rest were 0. The magnitude of $\Delta\theta_i$ impacts convergence speed ($0.001\pi$ to $0.05\pi$ recommended).

5. Experimental Setup

The experiments aim to demonstrate the effectiveness and applicability of QEA on the knapsack problem and compare its performance with conventional Genetic Algorithms (GAs).

5.1. Datasets

The experiments used strongly correlated sets of data for the knapsack problem. This means there's a strong positive relationship between the profit ($p_i$) and weight ($w_i$) of items, which can make the problem challenging for some algorithms. The item properties were defined as:

• $w_i = \mathrm{uniformly\_random}[1, 10]$ (weight of item $i$ is a random integer between 1 and 10, inclusive).

• $p_i = w_i + 5$ (profit of item $i$ is its weight plus 5).

  The knapsack capacity ($C$) was set to: $$C = \frac { 1 } { 2 } \sum _ { i = 1 } ^ { m } w _ { i }$$ This means the knapsack can hold approximately half of the total weight of all items, making it a non-trivial packing problem. The data were unsorted.

Three problem sizes were considered:

• 100 items ($m=100$)

• 250 items ($m=250$)

• 500 items ($m=500$)

  These datasets are standard benchmarks for the knapsack problem, allowing for a fair comparison of optimization algorithm performance. They are effective for validating the method's ability to handle increasing problem complexity.

5.2. Evaluation Metrics

The primary evaluation metric used in the paper is the profit ($f(\mathbf{x})$) of the selected items in the knapsack. Since the goal of the knapsack problem is to maximize profit, a higher profit value indicates a better solution.

The profit is calculated as: $$f ( \mathbf { x } ) = \sum _ { i = 1 } ^ { m } p _ { i } x _ { i }$$ where:

• $p_i$: The profit of item $i$.

• $x_i$: A binary variable, 1 if item $i$ is selected for the knapsack, 0 otherwise.

• $m$: The total number of items.

  The experiments reported the best, mean, and worst profit values found over 30 runs, along with the standard deviation ($\sigma$). Additionally, the elapsed time per run ($t$) was measured to compare computational efficiency. The convergence rate and the mean of average profits of the population over generations were also analyzed qualitatively through plots.

5.3. Baselines

The paper compared QEA against conventional Genetic Algorithms (CGAs) for the knapsack problem. Three main types of GA methods were considered, along with combinations:

1. GAs based on Penalty Functions: These GAs incorporate the knapsack capacity constraint directly into the fitness function by penalizing solutions that violate the constraint. The profit $f(\mathbf{x})$ is modified as: $$f ( \mathbf { x } ) = \sum _ { i = 1 } ^ { m } p _ { i } x _ { i } - Pen ( \mathbf { x } )$$ where $Pen(\mathbf{x})$ is a penalty function that increases as the constraint violation increases. Two types of penalties were tested:

   • Pen1 (Logarithmic Penalty): $$Pen _ { 1 } ( \mathbf { x } ) = \log _ { 2 } \left( 1 + \rho \left( \displaystyle \sum _ { i = 1 } ^ { m } w _ { i } x _ { i } - C \right) \right)$$
   • Pen2 (Linear Penalty): $$Pen _ { 2 } ( \mathbf { x } ) = \rho \left( \displaystyle \sum _ { i = 1 } ^ { m } w _ { i } x _ { i } - C \right)$$ In both cases, $\rho = \operatorname* { m a x } _ { i = 1 \cdots m } \{ p _ { i } / w _ { i } \}$ is used as a penalty coefficient, representing the maximum profit-to-weight ratio among all items.

2. GAs based on Repair Methods: These GAs generate solutions first, and if a solution violates the constraint, a repair algorithm modifies it to become feasible. The profit $f(\mathbf{x})$ is then evaluated on the repaired solution: $$f ( \mathbf { x } ) = \sum _ { i = 1 } ^ { m } p _ { i } x _ { i } ^ { \prime }$$ where $\mathbf{x}'$ is the repaired version of the original binary vector $\mathbf{x}$. The repair algorithms differed in how they selected items for removal from an overfilled knapsack:

   • Rep1 (Random Repair): Selects a random item from the knapsack to remove until the capacity is met.
   • Rep2 (Greedy Repair): Sorts items by decreasing profit-to-weight ratio and always removes the item with the lowest ratio (the last item in the sorted list) until the capacity is met.

3. GAs based on Decoders: These GAs use an indirect representation (e.g., integer strings) that is then decoded into a binary solution.

   • Dec (Random Decoding): Uses an ordinal representation where each chromosome component is an integer used to select an item from a list. The list order is random. This method was mentioned but not used extensively for parameter tuning due to longer evolution times and worse performance.

     Combined Baselines: The paper also tested combinations such as $Pen2+Rep1$ and $Pen2+Rep2$, indicating a hybrid approach using both a penalty function and a repair mechanism. The $Pen2+Rep2$ combination was identified as the best-performing CGA and was primarily used for the detailed comparison with QEA.

These baselines are representative of common approaches to handling constraints in GAs for combinatorial optimization problems.

5.3.1. Parameter Settings

5.3.1.1. QEA Parameters

• Population Sizes: QEA1 (1 individual), QEA2 (10 individuals), QEA3 (10 individuals).
• Migration Period: QEA2 used global migration every 1 generation. QEA3 used global migration every 100 generations and local migration every generation (between neighboring solutions in B(t)).
• Rotation Angles ($\Delta\theta_i$):
  • Initial tuning tested values of $0.0025\pi, 0.005\pi, 0.01\pi, 0.02\pi, 0.05\pi$ for $\theta_3$ and $-\theta_5$.
  • Selected values for main experiments: $\theta_3 = 0.01\pi$ and $\theta_5 = -0.01\pi$. Other $\theta$ values ($\theta_1, \theta_2, \theta_4, \theta_6, \theta_7, \theta_8$) were set to 0.

5.3.1.2. Conventional GA Parameters

• Population Sizes: 10 and 50 individuals.
• Mutation Probabilities: Tested 0.001, 0.01, 0.05, 0.1.
• Crossover Probabilities (Two-point crossover): Tested 0.001, 0.01, 0.05, 0.1, 0.3, 0.5.
• Selected Parameters for Comparison: Based on tuning, a mutation probability of 0.01 and a crossover probability of 0.01 were chosen for CGAs.

5.3.1.3. General Experimental Settings

• Number of Runs: All experiments were averaged over 30 independent runs.
• Maximum Generations: 1000 generations for all algorithms.

6. Results & Analysis

6.1. Core Results Analysis

The experiments aimed to evaluate QEA's performance against various configurations of conventional Genetic Algorithms (CGAs) on the knapsack problem, focusing on profit achieved, convergence speed, and behavior with small population sizes.

6.1.1. Parameter Tuning for QEA

The paper first conducted experiments to find appropriate settings for the rotation angles ($\theta_3$ and $\theta_5$) used in the Q-gate for the knapsack problem. This involved testing various magnitudes for $\theta_3$ and $-\theta_5$ (specifically $0.0025\pi, 0.005\pi, 0.01\pi, 0.02\pi, 0.05\pi$) across different QEA configurations (QEA1, QEA2, QEA3) and problem sizes (100, 250, 500 items).

The following figure (Figure 3 from the original paper) shows the results of QEA1, QEA2, and QEA3 on the knapsack problems with 100, 250, and 500 items for finding good parameter settings of $\theta_3$ and $\theta_5$:

Figure 3. Profit variations for QEA configurations with different angle parameters.

The results indicated that setting $\theta_3 = 0.01\pi$ and $\theta_5 = -0.01\pi$ provided the best profits across different problem sizes and QEA configurations. It was noted that cases with equal magnitudes for $\theta_3$ and $-\theta_5$ performed better.

6.1.2. Parameter Tuning for Conventional GAs

A similar extensive tuning process was undertaken for CGAs to identify optimal mutation and crossover probabilities. This involved 288 experiments per problem size (24 parameter settings $\times$ 6 CGAs $\times$ 2 population sizes) to find the combination that yielded the maximum profit.

The following figure (Figure 4 from the original paper) shows the results of six CGAs on the knapsack problems with 100, 250, and 500 items to find good parameter settings:

Figure 4. Profit variations for different CGA configurations with various mutation and crossover probabilities.

From these tests, mutation and crossover probabilities around 0.01 were found to be optimal for most CGAs, with the specific combinations of (0.01, 0.001), (0.01, 0.01), and (0.01, 0.05) giving the best results. For the final comparison, 0.01 for both mutation and crossover probabilities was selected for CGAs. Among the tested CGAs, $Pen2+Rep2$ (linear penalty function combined with greedy repair) consistently outperformed others.

6.1.3. Comparison of QEA and CGA Performance

The main comparison focused on QEA (QEA1, QEA2, QEA3) against the best-performing CGA, $Pen2+Rep2$ (denoted as P2R2), with population sizes of 10 and 50.

The following are the results from Table II of the original paper:

Table II. Experimental Results of the Knapsack Problem: The number of items 100, 250, and 500, the maximum number of generations 1000, the number of runs 30. The parenthesized values are the population sizes. P2R2 means the algorithm implemented by Pen2+Rep2, and b.m.W. mean best, mean, and worst, respectively. t (seconds/run) and $\sigma$ represent the elapsed time per run and the standard deviation, respectively.

Analysis of Table II:

• Overall Performance: QEAs consistently yielded better results (higher best, mean, and worst profits) compared to P2R2, especially for larger problem sizes (250 and 500 items).

• Small Population Advantage: QEA1 (population size 1) found better solutions than P2R2 (population size 10) for 250 and 500 items, and comparable solutions for 100 items. This highlights QEA's ability to perform well even with a minimal population, owing to its Q-bit representation.

• Computational Efficiency: QEA1 had significantly lower elapsed time per run (0.021s for 100 items, 0.055s for 250, 0.117s for 500) compared to P2R2(10) (0.154s, 0.357s, 0.706s) and P2R2(50) (0.786s, 1.804s, 3.559s). This indicates QEA is more efficient, particularly when considering its superior performance with fewer individuals.

• Stability: QEAs generally showed lower standard deviations ($\sigma$) for mean profits, suggesting more stable and consistent performance across multiple runs. QEA3 had the lowest $\sigma$ for all problem sizes, indicating high reliability.

  The following figure (Figure 5 from the original paper) shows the comparison of QEAs and CGA on the knapsack problem:

  Figure 5. Comparison of QEAs and CGA on the knapsack problem. The CGA is Pen2+Rep2.

  Analysis of Figure 5:

• Convergence Rate and Profit Amount: QEAs (QEA1, QEA2, QEA3) demonstrate significantly faster convergence rates and achieve much higher final profit amounts compared to CGA ($Pen2+Rep2$).

• Premature Convergence: The CGA (P2R2) shows clear signs of premature convergence, with its mean of average profits flattening out early and maintaining a nearly constant (suboptimal) profit after a certain number of generations. This suggests a loss of diversity and inability to further improve solutions.

• Sustained Improvement in QEAs: QEAs, conversely, continue to improve their average profits up to 1000 generations, indicating that they maintain population diversity and effectively explore the search space without getting stuck.

• Impact of Population Size and Migration:

  • QEA1 (single individual) shows a slower initial convergence than QEA2 and QEA3, which use 10 individuals. However, its final profit is still higher than CGA.
  • QEA3 (with global migration every 100 generations and local migration every generation) initially has a slower convergence than QEA2 (global migration every generation). However, QEA3 eventually outperforms QEA2 in terms of final profit after about 500 generations. This suggests that a less frequent global migration combined with continuous local migration helps maintain better population diversity over longer runs, preventing early convergence to a local optimum and allowing for continued exploration.

6.2. Ablation Studies / Parameter Analysis

6.2.1. Verification of Angle Selection

The paper conducted a detailed verification of the heuristic choice of angle parameters for the rotation gate in the Q-gate ($\Delta\theta_i$). This was done using QEA1 on a 100-item knapsack problem, systematically testing $3^8$ possible combinations of values ($0, 0.005\pi, -0.005\pi$) for the eight angle parameters ($\theta_1$ to $\theta_8$) in Table I.

The following figure (Figure 6 from the original paper) shows the profit values of a quantum-inspired evolutionary algorithm under different parameters:

Figure 6. Profit values of 1024 cases in the knapsack problem with ten items obtained by a simple calculation. The vertical axis is the profit values of the knapsack, and the horizontal axis is the number of 1024 cases selected as a subset from ten items. The best profit satisfying the capacity constraint is marked with O.

The results shown in Figure 6 (a)-(f) confirmed the intuitive reasoning:

• The angles associated with conditions where $f(\mathbf{x}) \ge f(\mathbf{b})$ (i.e., $\theta_2, \theta_4, \theta_6, \theta_8$) had little effect on the results, suggesting they could be set to 0.
• For conditions where $f(\mathbf{x}) < f(\mathbf{b})$:
  • If $x_i=0, b_i=1$, a positive $\Delta\theta_i$ (like $\theta_3 = 0.005\pi$) was beneficial to increase the probability of bit '1'.
  • If $x_i=1, b_i=0$, a negative $\Delta\theta_i$ (like $\theta_5 = -0.005\pi$) was beneficial to increase the probability of bit '0'. This systematic verification validated the heuristic choices for $\Delta\theta_i$ (e.g., $[0 * p * n * 0 *]^T$, where $p$ is positive, $n$ is negative, and * indicates little effect).

6.3. Investigation of QEA Characteristics

To understand how QEA balances exploration and exploitation, a simple 10-item knapsack problem was analyzed. This problem has $2^{10} = 1024$ possible solutions, allowing for a complete enumeration of profit values and direct observation of probability distributions.

The following figure (Figure 7 from the original paper) shows the profit values of 1024 cases in the knapsack problem with ten items obtained by a simple calculation:

Figure 7. Profit values of 1024 cases in the knapsack problem with ten items obtained by a simple calculation. The vertical axis is the profit values of the knapsack, and the horizontal axis is the number of 1024 cases selected as a subset from ten items. The best profit satisfying the capacity constraint is marked with O.

Figure 7 shows the profit distribution for all 1024 possible solutions, with the optimal feasible solution marked.

The following figure (Figure 8, 9 from the original paper) shows the probabilities of 1024 solutions using the Q-bit individual at different generations:

该图像是多个概率分布图，展示了不同案例编号下的概率变化，标记为(a)至(f)。这些图表显示了收敛趋势和波动性，表明量子启发的进化算法在解决组合优化问题时的性能表现。

Figure 8 & 9. Probability distributions of 1024 solutions for a 10-item knapsack problem using a single Q-bit individual at various generations.

Analysis of Figures 8 and 9:

• Initial Random Search (Generation 0 - implicit, or Generation 10 in early stage): At initialization, all $2^m$ states have equal probability ($1/2^m$). This implies an initial random search behavior, where all solutions are equally likely to be observed. Figure 8(a) and (b) (conceptually, for generation 10) show how the probabilities of the 1024 solutions begin to align with the overall profit distribution from Figure 7, meaning QEA starts with a broad exploration.

• Transition to Local Search (Generations 20-50): As generations progress (Figure 8(c)-(e)), the probabilities of solutions with higher profits begin to increase significantly, forming distinct peaks. This indicates that QEA is starting to focus its search efforts on more promising regions, gradually transitioning from exploration to local search or exploitation.

• Convergence to Optimal Solution (Generations 100-300): By generation 100 (Figure 9(g)), the probabilities of most suboptimal solutions decrease, while the peaks corresponding to better solutions become more pronounced. At generation 300 (Figure 9(h)), the probability of the single best solution dominates (over 0.9), while others are near 0. This demonstrates a strong convergence towards the optimal solution.

  Conclusion on Characteristics: The experimental investigation confirms that QEA inherently balances exploration and exploitation. It starts with a global search due to the initial uniform superposition of Q-bits. As the Q-gates update the probabilities based on observed fitness, the algorithm automatically shifts towards local search and exploitation of promising areas, eventually converging to high-quality solutions.

6.4. Termination Condition

The probabilistic nature of QEA allows for a novel termination condition. Instead of relying solely on a maximum number of generations, the algorithm can terminate when the probability of the overall best solution $\mathbf{b}$ exceeds a certain threshold $\gamma$ (e.g., $Prob(b) > γ$, where $0 < \gamma < 1$). The probability of a binary solution $\mathbf{b}$ can be calculated by multiplying the probabilities of its individual Q-bits. For example, if $\mathbf{b} = 1010$, then $\mathrm{Prob}(\mathbf{b}) = |\beta_1|^2 |\alpha_2|^2 |\beta_3|^2 |\alpha_4|^2$. This allows for dynamic termination based on the confidence that the algorithm has found the optimal (or near-optimal) solution.

7. Conclusion & Reflections

7.1. Conclusion Summary

This paper successfully introduced the Quantum-Inspired Evolutionary Algorithm (QEA), a novel optimization method that leverages concepts from quantum computing for implementation on classical computers. The core innovations include the Q-bit for probabilistic representation, allowing for a superposition of states and enhanced population diversity, and the Q-gate (specifically a rotation gate) as a variation operator to guide the evolutionary process. The algorithm's structure incorporates initialization, observation (to generate binary solutions), fitness evaluation, Q-gate updates, and migration for further diversity management.

Experiments on the knapsack problem demonstrated QEA's significant advantages over conventional Genetic Algorithms (GAs). QEA exhibited superior performance in terms of achieving higher profits, faster convergence rates, and maintaining population diversity to avoid premature convergence. Crucially, QEA performed effectively even with a very small population size (e.g., a single individual), making it computationally efficient. Analysis of its characteristics revealed an inherent mechanism that dynamically balances exploration and exploitation, starting with a broad search and gradually focusing on promising solutions. The paper also proposed a probability-based termination condition.

7.2. Limitations & Future Work

The paper doesn't explicitly list limitations within a dedicated section, but some can be inferred:

• Heuristic Angle Parameter Tuning: While the paper systematically verified the $Δθ_i$ selection, the initial choice of $θ$ values (e.g., $0.01\pi$) and their signs for the Q-gate remains largely heuristic. Developing a more adaptive or problem-independent method for determining these rotation angles could improve generalizability.

• Problem-Specific Repair Mechanism: The repair procedure for the knapsack problem is specific to handling capacity constraints. For other combinatorial optimization problems with different constraint types, a new, problem-specific repair mechanism would be required, which might add complexity.

• No Direct Quantum Speedup: As a "quantum-inspired" algorithm running on classical hardware, QEA does not benefit from the exponential speedups that true quantum algorithms might offer. Its advantages stem from improved representation and search strategy, not quantum parallelism.

• Scalability to Extremely Large Problems: While shown to perform well on problems up to 500 items, the ultimate scalability of QEA for extremely large-scale combinatorial optimization problems (millions of variables) would need further investigation.

  Potential future research directions suggested implicitly or explicitly:

• Application to Other Problems: Testing QEA on a wider range of combinatorial optimization problems (e.g., traveling salesman problem, scheduling problems) to assess its general applicability and robustness.

• Adaptive Angle Control: Research into more sophisticated, adaptive mechanisms for controlling the rotation angles of the Q-gates rather than fixed or heuristically chosen values.

• Further Quantum Concepts: Exploring the integration of other quantum-inspired concepts (e.g., entanglement, interference effects beyond simple crossover) into QEA to potentially enhance its capabilities.

• Hybrid Approaches: Combining QEA with other metaheuristics or local search techniques to create even more powerful hybrid algorithms.

7.3. Personal Insights & Critique

This paper presents a foundational contribution to the field of quantum-inspired evolutionary computation. The core idea of using a probabilistic Q-bit representation is elegant and powerful. It effectively addresses a long-standing challenge in EAs: maintaining population diversity and balancing exploration and exploitation, especially crucial for small populations. The ability of QEA to outperform conventional GAs even with a single individual is a strong testament to the efficiency of this representation.

One of the most inspiring aspects is how the paper translates abstract quantum mechanical principles into practical, classical algorithmic components. The Q-bit acts as an intelligent, dynamic probabilistic distribution over the solution space, and the Q-gate provides a controlled, directed way to evolve this distribution. This metaphorical borrowing of ideas from a different scientific domain is a hallmark of innovative research.

However, a point of critique could be the heavy reliance on heuristic parameter tuning for the Q-gate's rotation angles. While the paper provides a systematic verification, the process of selecting the base theta values might still involve trial and error for new problems. Future work could benefit from more theoretically grounded or self-adaptive mechanisms for these parameters, similar to how mutation rates can be adapted in some GAs. Additionally, while the knapsack problem is a good benchmark, exploring its performance on problems with different structural properties (e.g., highly deceptive landscapes) would further solidify its robustness.

The conceptual framework of QEA could be transferred or applied to other domains where probabilistic modeling and efficient search are critical. For instance, in reinforcement learning, Q-bit-like representations could be used to model probabilistic policies, where Q-gates could act as policy update mechanisms. In machine learning, it could inspire new ways to represent and evolve neural network weights or architectures. The idea of implicitly representing a large solution space with a compact probabilistic structure is broadly applicable beyond combinatorial optimization.