A multiagent evolutionary algorithm for combinatorial optimization problems

Area of Science:

• Computational Intelligence
• Optimization Algorithms
• Artificial Intelligence

Background:

• Combinatorial optimization problems (CmOPs) present significant computational challenges.
• Evolutionary algorithms (EAs) are widely used but struggle with complex problem structures.
• Existing methods often lack efficiency in solving large-scale and deceptive CmOPs.

Purpose of the Study:

• To introduce a novel algorithm, MultiAgent EA for CmOPs (MAEA-CmOPs), integrating multiagent systems and EAs.
• To enhance the performance of EAs in solving difficult CmOPs, including deceptive and hierarchical problems.
• To analyze the theoretical convergence properties and practical performance of the proposed MAEA-CmOPs.

Main Methods:

• Development of MAEA-CmOPs, featuring agents in a lattice environment competing and utilizing domain knowledge.
• Theoretical analysis to demonstrate convergence to global optimum solutions.
• Experimental validation using various deceptive (strong, weak, overlapping linkage) and hierarchical (treelike structures) CmOPs.

Main Results:

• MAEA-CmOPs demonstrated superior performance compared to other algorithms on deceptive and hierarchical problems.
• The algorithm exhibits a fast convergence rate.
• Effective handling of large-scale problems (thousands of dimensions) with good performance and low computational cost.

Conclusions:

• MAEA-CmOPs is a highly effective algorithm for solving challenging combinatorial optimization problems.
• The integration of multiagent systems and EAs provides a powerful framework for optimization.
• The algorithm's polynomial time complexity scaling ensures efficiency for large-scale applications.