A pattern-based evolving mechanism for genetic algorithm to solve combinatorial optimization problems

Qing Wang, Kai Leung Yung, Wai Hung Ip

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

1 Citation (Scopus)

Abstract

The combinatorial optimization problem always is ubiquitous in various applications and has been proved to be well known NP-hard problem that classical mathematical methods cannot solve within the polynomial time. To solve it, many approaches have been developed to find best or near best solutions. As one of such approaches, genetic algorithm is well known as being able to find satisfied solution within acceptable time, it is controlled by evolving mechanism to achieve optimization searching in the solutions space. In this paper, we propose a new evolving mechanism for GA to improve the solution quality and searching efficiency as well. This evolving mechanism can extract a generalized pattern from elite individuals in the whole population. The pattern is used to determine the selection probability to experience the genetic operations such as crossover, mutation, replication, etc. moreover, the evolving mechanism includes a replacement mechanism to substitute the worse individual for the potential excellent individual to expand searching space. The computation results show that the proposed evolving mechanism can work effectively and find satisfactory solutions better than traditional evolving mechanisms, even though the solution space increases with the problem size.
Original languageEnglish
Title of host publicationSMCia 2003 - Proceedings of the 2003 IEEE International Workshop on Soft Computing in Industrial Applications
PublisherIEEE
Pages97-101
Number of pages5
ISBN (Electronic)0780378555, 9780780378551
DOIs
Publication statusPublished - 1 Jan 2003
Event2003 IEEE International Workshop on Soft Computing in Industrial Applications, SMCia 2003 - Binghamton University, Binghamton, United States
Duration: 23 Jun 200325 Jun 2003

Conference

Conference2003 IEEE International Workshop on Soft Computing in Industrial Applications, SMCia 2003
CountryUnited States
CityBinghamton
Period23/06/0325/06/03

Keywords

  • Evolution (biology)
  • Genetic algorithms
  • Genetic mutations
  • Mathematics
  • NP-hard problem
  • Optimization methods
  • Polynomials
  • Resource management
  • State-space methods
  • Systems engineering and theory

ASJC Scopus subject areas

  • Software
  • Computational Theory and Mathematics
  • Industrial and Manufacturing Engineering
  • Artificial Intelligence

Cite this