Related Experiment Video
Updated: Nov 27, 2025
05:30
Large Scale Energy Efficient Sensor Network Routing Using a Quantum Processor Unit
Published on: September 8, 2023
952
Quantum-Inspired Evolutionary Approach for the Quadratic Assignment Problem
Wojciech Chmiel1, Joanna Kwiecień1
1Faculty of Electrical Engineering, Automatics, Computer Science and Biomedical Engineering, AGH University of Science and Technology, al. Mickiewicza 30, 30-059 Kraków, Poland.
Entropy (Basel, Switzerland)
|December 3, 2020
Summary
This study introduces a quantum-inspired evolutionary algorithm to solve the quadratic assignment problem, aiming for minimal assignment costs. The developed algorithm demonstrates satisfactory performance in finding optimal solutions.
Area of Science:
- Optimization algorithms
- Computational intelligence
- Combinatorial optimization
Background:
- The quadratic assignment problem (QAP) is a complex combinatorial optimization problem with significant real-world applications.
- Traditional algorithms often struggle with the NP-hard nature of QAP, necessitating novel approaches.
- Quantum-inspired evolutionary algorithms offer a promising paradigm for tackling such challenging problems.
Purpose of the Study:
- To adapt and apply a quantum-inspired evolutionary algorithm (QIEA) for solving the quadratic assignment problem.
- To investigate the integration of quantum principles into crossover and mutation operators within the evolutionary framework.
- To evaluate the effectiveness of the proposed QIEA for minimizing assignment costs in QAP.
Main Methods:
- Development of a specialized quantum-inspired evolutionary algorithm tailored for the quadratic assignment problem.
- Implementation of novel crossover and mutation operators incorporating quantum principles.
- Systematic testing and performance evaluation of the algorithm on QAP instances.
- Analysis of the impact of selected algorithm parameters on solution quality.
Main Results:
- The proposed quantum-inspired evolutionary algorithm demonstrated satisfactory performance in converging towards optimal solutions for the quadratic assignment problem.
- The adaptation of quantum principles within evolutionary operators proved effective for QAP.
- Parameter sensitivity analysis provided insights into optimizing the algorithm's performance.
- The approach shows potential for efficient cost minimization in QAP.
Conclusions:
- Quantum-inspired evolutionary algorithms are a viable and effective method for addressing the quadratic assignment problem.
- The tailored QIEA offers a competitive approach for finding minimal assignment costs.
- Further research can explore advanced quantum principles and larger QAP instances.
Related Concept Videos
01:29Quadratic Equations
113
A quadratic equation is an algebraic expression where a variable is raised to the second power and combined with its first power and a constant; all equated to zero. These equations are frequently used to model relationships involving area, motion, and optimization. The general representation of a quadratic equation iswhere a, b, and c are real values, and a is nonzero to ensure the presence of the squared term.One method for solving a quadratic equation involves rewriting it as a product of...
113
01:23Quadratic Models
76
Quadratic models are mathematical representations used to describe relationships in which the rate of change changes at a constant rate. These models appear in a wide variety of natural and engineered systems, especially those involving motion, forces, and optimization. One common application is analyzing the vertical motion of objects influenced by gravity, such as a ball thrown into the air.In such scenarios, the object's height changes over time in a curved pattern, rising to a maximum point...
76
01:29Quadratic Equations in the Complex Number System
128
A quadratic equation in the form ax2+bx+c=0 can have solutions that vary in nature depending on the value of the discriminant, b2−4ac. In this expression, a is the coefficient of the quadratic term x2, b is the coefficient of the linear term x, and c is the constant term. When the discriminant is negative, the equation has no real number solutions. However, by introducing complex numbers through the imaginary unit i, defined by i=-1, these equations can still be solved.The square root of...
128
01:30Gaussian Elimination: Problem Solving
66
Systems of linear equations in several variables are pivotal in modeling complex scenarios involving multiple unknowns and constraints. Such systems are widely used in various fields to represent relationships where several conditions must be simultaneously satisfied. Each variable in the system corresponds to an unknown quantity, while each equation imposes a linear constraint, leading to a structured approach for analyzing and solving real-world problems.A system of three equations with three...
66
02:43Quantum Numbers
47.5K
It is said that the energy of an electron in an atom is quantized; that is, it can be equal only to certain specific values and can jump from one energy level to another but not transition smoothly or stay between these levels.
47.5K
01:17Ampere-Maxwell's Law: Problem-Solving
939
A parallel-plate capacitor with capacitance C, whose plates have area A and separation distance d, is connected to a resistor R and a battery of voltage V. The current starts to flow at t = 0. What is the displacement current between the capacitor plates at time t? From the properties of the capacitor, what is the corresponding real current?
To solve the problem, we can use the equations from the analysis of an RC circuit and Maxwell's version of Ampère's law.
For the first part of the...
To solve the problem, we can use the equations from the analysis of an RC circuit and Maxwell's version of Ampère's law.
For the first part of the...
939