Automatically assigned DDC number: 0063

Manually assigned DDC number: 00631

Number of references: 0

Title: An Evolutionary Heuristic for the Maximum Independent Set Problem

Author:

Author:

Subject: Thomas Back,Sami Khuri An Evolutionary Heuristic for the Maximum Independent Set Problem

Description: The results obtained from the application of a genetic algorithm, GENEsYs, to the NP-complete maximum independent set problem are reported in this work. In contrast to many other genetic algorithm based approaches that use domain-specific knowledge, the approach presented here relies on a graded penalty term component of the fitness function to penalize infeasible solutions. The method is applied to several large problem instances of the maximum independent set problem. The results clearly indicate that genetic algorithms can be successfully used as heuristics for finding good approximative solutions for this highly constrained optimization problem. I. Introduction Once the NP-hardness of a combinatorial optimization problem is established, the search for an optimal solution is abandoned. The goal then becomes one of finding a good heuristic, i.e. a polynomial running time algorithm that can find solutions close to the optimal. In most cases, traditional heuristics are problem depende...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1996-08-02

Pubyear: 1994

Format: ps

Identifier: http://citeseer.ist.psu.edu/140608.html

Source: http://ls11-www.informatik.uni-dortmund.de/people/baeck/papers/wcci94-graph.ps.gz

Language: en

Rights: unrestricted

Graph

<?xml   version="1.0"   encoding="UTF-8"?>

<references_metadata>

      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="An   Evolutionary   Heuristic   for   the   Maximum   Independent   Set   Problem">

            <identifier   Org="ISBN:0750306653"   Paper_ID="SELF"   Extracted="0750306653"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0750308958"   Paper_ID="SELF"   Extracted="0750308958"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0780318994"   Paper_ID="SELF"   Extracted="0780318994"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0780329023"   Paper_ID="SELF"   Extracted="0780329023"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0780355369"   Paper_ID="SELF"   Extracted="0780355369"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0792343514"   Paper_ID="SELF"   Extracted="0792343514"   DDC="519.7/6"   Normalized_DDC="51976"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0792359240"   Paper_ID="SELF"   Extracted="0792359240"   DDC="519.6/4"   Normalized_DDC="51964"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:084931075X"   Paper_ID="SELF"   Extracted="084931075X"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:1558608788"   Paper_ID="SELF"   Extracted="1558608788"   DDC="006.31"   Normalized_DDC="00631"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540009760"   Paper_ID="SELF"   Extracted="3540009760"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540442650"   Paper_ID="SELF"   Extracted="3540442650"   DDC="006.3/2"   Normalized_DDC="00632"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540594795"   Paper_ID="SELF"   Extracted="3540594795"   DDC="005.1/1"   Normalized_DDC="00511"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540611088"   Paper_ID="SELF"   Extracted="3540611088"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540612866"   Paper_ID="SELF"   Extracted="3540612866"   DDC="006.3/3"   Normalized_DDC="00633"   Normalized_Weight="0.07142857142857142"   />

      </rec>

</references_metadata>

www.000webhost.com