Automatically assigned DDC number: 00631

Manually assigned DDC number: 00631

Number of references: 4

Title: A Parallel Genetic Algorithm for the Set Partitioning Problem

Author:

Subject: David Levine A Parallel Genetic Algorithm for the Set Partitioning Problem

Description: . This paper describes a parallel genetic algorithm developed for the solution of the set partitioning problem---a difficult combinatorial optimization problem used by many airlines as a mathematical model for flight crew scheduling. The genetic algorithm is based on an island model where multiple independent subpopulations each run a steady-state genetic algorithm on their own subpopulation and occasionally fit strings migrate between the subpopulations. Tests on forty real-world set partitioning problems were carried out on up to 128 nodes of an IBM SP1 parallel computer. We found that performance, as measured by the quality of the solution found and the iteration on which it was found, improved as additional subpopulations were added to the computation. With larger numbers of subpopulations the genetic algorithm was regularly able to find the optimal solution to problems having up to a few thousand integer variables. In two cases, high-quality integer feasible solutions were found f...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1994-09-26

Pubyear: 1994

Format: ps

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

Source: ftp://info.mcs.anl.gov/pub/tech_reports/reports/P458.ps.Z

Language: en

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

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

<references_metadata>

      <rec   ID="/142964.html"   Type="techreport"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="{A}   {P}arallel   {G}enetic   {A}lgorithm   for   the   {S}et   {P}artitioning   {P}roblem,"   />

      <rec   ID="/4527.html"   Type="inproceedings"   CiteSeer_Book="Proceedings   of   the   Fourth   International   Conference   on   Genetic   Algorithms"   CiteSeer_Volume=""   Title="On   the   virtues   of   parameterized   uniform   crossover,">

            <identifier   Org="ISBN:0262133172"   Paper_ID="/4527.html"   Extracted="0262133172"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:0262692813"   Paper_ID="/4527.html"   Extracted="0262692813"   DDC="570/.1/13"   Normalized_DDC="570113"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:0387234608"   Paper_ID="/4527.html"   Extracted="0387234608"   DDC="658.4/03"   Normalized_DDC="658403"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:0471669512"   Paper_ID="/4527.html"   Extracted="0471669512"   DDC="003/.3"   Normalized_DDC="0033"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:0521792479"   Paper_ID="/4527.html"   Extracted="0521792479"   DDC="620/.0042"   Normalized_DDC="6200042"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:0750306645"   Paper_ID="/4527.html"   Extracted="0750306645"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:0750308958"   Paper_ID="/4527.html"   Extracted="0750308958"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:0784406367"   Paper_ID="/4527.html"   Extracted="0784406367"   DDC="624.1/771"   Normalized_DDC="6241771"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:0849305888"   Paper_ID="/4527.html"   Extracted="0849305888"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:1402006322"   Paper_ID="/4527.html"   Extracted="1402006322"   DDC="519.7/6"   Normalized_DDC="51976"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:1558602089"   Paper_ID="/4527.html"   Extracted="1558602089"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:1558604871"   Paper_ID="/4527.html"   Extracted="1558604871"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:1558605592"   Paper_ID="/4527.html"   Extracted="1558605592"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540401849"   Paper_ID="/4527.html"   Extracted="3540401849"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:354040211X"   Paper_ID="/4527.html"   Extracted="354040211X"   DDC="006.3/2"   Normalized_DDC="00632"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540410945"   Paper_ID="/4527.html"   Extracted="3540410945"   DDC="006.3/3"   Normalized_DDC="00633"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540694315"   Paper_ID="/4527.html"   Extracted="3540694315"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540728686"   Paper_ID="/4527.html"   Extracted="3540728686"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540762140"   Paper_ID="/4527.html"   Extracted="3540762140"   DDC="670/.285/63"   Normalized_DDC="67028563"   Normalized_Weight="0.05263157894736842"   />

      </rec>

      <rec   ID="/251626.html"   Type="inproceedings"   CiteSeer_Book="Proc   of   the   Fifth   Int   Conf   on   Genetic   Algorithms"   CiteSeer_Volume=""   Title="Expected   Allele   Coverage   and   the   Role   of   Mutation   in   Genetic   Algorithms,">

            <identifier   Org="ISBN:0780318994"   Paper_ID="/251626.html"   Extracted="0780318994"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0780319664"   Paper_ID="/251626.html"   Extracted="0780319664"   />

            <identifier   Org="ISBN:0780324617"   Paper_ID="/251626.html"   Extracted="0780324617"   />

            <identifier   Org="ISBN:0780336860"   Paper_ID="/251626.html"   Extracted="0780336860"   DDC="670.42/7"   Normalized_DDC="670427"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0780339495"   Paper_ID="/251626.html"   Extracted="0780339495"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0780370902"   Paper_ID="/251626.html"   Extracted="0780370902"   />

            <identifier   Org="ISBN:0792376544"   Paper_ID="/251626.html"   Extracted="0792376544"   DDC="519.3"   Normalized_DDC="5193"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0849325390"   Paper_ID="/251626.html"   Extracted="0849325390"   />

            <identifier   Org="ISBN:1558602992"   Paper_ID="/251626.html"   Extracted="1558602992"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:1558605592"   Paper_ID="/251626.html"   Extracted="1558605592"   />

            <identifier   Org="ISBN:1558606114"   Paper_ID="/251626.html"   Extracted="1558606114"   />

            <identifier   Org="ISBN:3540224947"   Paper_ID="/251626.html"   Extracted="3540224947"   DDC="153.42"   Normalized_DDC="15342"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3540584846"   Paper_ID="/251626.html"   Extracted="3540584846"   />

            <identifier   Org="ISBN:3540594965"   Paper_ID="/251626.html"   Extracted="3540594965"   DDC="574/.01/13"   Normalized_DDC="5740113"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3540604693"   Paper_ID="/251626.html"   Extracted="3540604693"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:354061723X"   Paper_ID="/251626.html"   Extracted="354061723X"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3540789863"   Paper_ID="/251626.html"   Extracted="3540789863"   />

            <identifier   Org="ISBN:9810236026"   Paper_ID="/251626.html"   Extracted="9810236026"   DDC="575.1"   Normalized_DDC="5751"   Normalized_Weight="0.1"   />

      </rec>

      <rec   ID="/531499.html"   Type="incollection"   CiteSeer_Book="Foundations   of   Genetic   Algorithms   2"   CiteSeer_Volume=""   Title="An   Executable   Model   of   a   simple   Genetic   Algorithm,">

            <identifier   Org="ISBN:0444512837"   Paper_ID="/531499.html"   Extracted="0444512837"   DDC="541.2/2/0285"   Normalized_DDC="541220285"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:0471678066"   Paper_ID="/531499.html"   Extracted="0471678066"   DDC="519.6"   Normalized_DDC="5196"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:0750308958"   Paper_ID="/531499.html"   Extracted="0750308958"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:0780355369"   Paper_ID="/531499.html"   Extracted="0780355369"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:0792374665"   Paper_ID="/531499.html"   Extracted="0792374665"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:0792399331"   Paper_ID="/531499.html"   Extracted="0792399331"   />

            <identifier   Org="ISBN:1402072635"   Paper_ID="/531499.html"   Extracted="1402072635"   />

            <identifier   Org="ISBN:1402075243"   Paper_ID="/531499.html"   Extracted="1402075243"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:1558602631"   Paper_ID="/531499.html"   Extracted="1558602631"   DDC="511.8"   Normalized_DDC="5118"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:1558602992"   Paper_ID="/531499.html"   Extracted="1558602992"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:1558603700"   Paper_ID="/531499.html"   Extracted="1558603700"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:1558604871"   Paper_ID="/531499.html"   Extracted="1558604871"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:1558605592"   Paper_ID="/531499.html"   Extracted="1558605592"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:1842652028"   Paper_ID="/531499.html"   Extracted="1842652028"   />

            <identifier   Org="ISBN:3540290060"   Paper_ID="/531499.html"   Extracted="3540290060"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540584838"   Paper_ID="/531499.html"   Extracted="3540584838"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:354061723X"   Paper_ID="/531499.html"   Extracted="354061723X"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540641696"   Paper_ID="/531499.html"   Extracted="3540641696"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.06666666666666667"   />

      </rec>

      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="A   Parallel   Genetic   Algorithm   for   the   Set   Partitioning   Problem">

            <identifier   Org="ISBN:0471678066"   Paper_ID="SELF"   Extracted="0471678066"   DDC="519.6"   Normalized_DDC="5196"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:0780363752"   Paper_ID="SELF"   Extracted="0780363752"   />

            <identifier   Org="ISBN:0780378040"   Paper_ID="SELF"   Extracted="0780378040"   />

            <identifier   Org="ISBN:0792372212"   Paper_ID="SELF"   Extracted="0792372212"   DDC="519.7"   Normalized_DDC="5197"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:0792397002"   Paper_ID="SELF"   Extracted="0792397002"   DDC="519.3"   Normalized_DDC="5193"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:155860605X"   Paper_ID="SELF"   Extracted="155860605X"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.09090909090909091"   />

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

            <identifier   Org="ISBN:354020167X"   Paper_ID="SELF"   Extracted="354020167X"   DDC="620/.0015/196"   Normalized_DDC="6200015196"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3540219463"   Paper_ID="SELF"   Extracted="3540219463"   DDC="004.35"   Normalized_DDC="00435"   Normalized_Weight="0.09090909090909091"   />

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

            <identifier   Org="ISBN:3540290060"   Paper_ID="SELF"   Extracted="3540290060"   />

            <identifier   Org="ISBN:3540305068"   Paper_ID="SELF"   Extracted="3540305068"   />

            <identifier   Org="ISBN:3540435913"   Paper_ID="SELF"   Extracted="3540435913"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3540603824"   Paper_ID="SELF"   Extracted="3540603824"   DDC="658.4/033"   Normalized_DDC="6584033"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3540634762"   Paper_ID="SELF"   Extracted="3540634762"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3540755543"   Paper_ID="SELF"   Extracted="3540755543"   />

            <identifier   Org="ISBN:3540769307"   Paper_ID="SELF"   Extracted="3540769307"   />

      </rec>

</references_metadata>