Applying statistical mechanics to search problems in AI, decisions and optimization has been one of the powerful channels to solve NP-hard problems. Extensive analytical and experimental research has shown that the &q...
详细信息
Applying statistical mechanics to search problems in AI, decisions and optimization has been one of the powerful channels to solve NP-hard problems. Extensive analytical and experimental research has shown that the "phase transition" phenomenon in search space is often associated with the hardness of complexity. A Bak-Sneppen(BS) model based general-purpose heuristic method, called extremaloptimization(EO), proposed by Boettcher and Percus from physics society may perform very well, especially near the phasetransitions in compared with other optimization methods, e.g., genetic algorithm and simulated annealing, etc. To actuate more extensive investigations on this new optimization approach particularly in control, computer and optimization communities,this survey reviews the latest research results from fundamental to practice about the connection between computationalcomplexity and phasetransitions. Then, further introduces the concepts, fundamentals, algorithms and applications of EO from its capability of self-organized criticality, backbone analysis and co-evolution moving to a far-from-equilibrium state. Finally, the concluding remarks with suggested future research are illustrated.
暂无评论