An Optimization Algorithm Based on the Small-World Phenomenon

• Brief introduction:

In the 1960s, Stanley Milgram performed a mail-delivery experiment to trace out the short paths through the social networks in the United States. The results demonstrated a small-world phenomenon because any two individuals in the social network were linked by a short chain of acquaintances (popularly known as “six degrees of separation”). In 1998, Duncan Watts and Steve Strogatz published the paper “Collective Dynamics of Small-World Networks” in Nature, in which the small-world phenomena were explained by a network with dominant local connections and a few long-range links. Since then, the small-world phenomena have become a hotspot in theoretical discussion of Artificial Intelligence (AI) and Complexity. Meanwhile, the small-world network has been successfully applied to a variety of areas, such as computer networks, AIDS diffusion forecast and dynamics of biological protein networks. However, little reports have been found in the field of optimization algorithms. In an optimization problem, the search space is composed of all potential solutions and the optimization can be viewed as a process in which information transmits from a candidate solution to the optimal solution. Inspired by the local and long-range connections, which support the small-world phenomena, we will create a local search operator and a long-range search operator and then construct a search algorithm and discuss the optimization mechanics. Algorithm Applications will focus on function optimization and Knapsack problems.

• Group members:

Haifeng Du, Jie Shao and Chen Hou