{"id":2069,"date":"2025-10-26T17:43:40","date_gmt":"2025-10-26T16:43:40","guid":{"rendered":"https:\/\/xeddixx.cluster029.hosting.ovh.net\/?page_id=2069"},"modified":"2025-10-27T10:07:01","modified_gmt":"2025-10-27T09:07:01","slug":"gga","status":"publish","type":"page","link":"https:\/\/www.francq.info\/index.php\/gga\/","title":{"rendered":"Grouping Genetic Algorithms"},"content":{"rendered":"\n

Abstract<\/h4>\n\n\n\n

The Grouping Genetic Algorithms (GGA) are a kind of\u00a0Genetic Algorithms (GA)<\/a>\u00a0applicable to solve grouping problems.<\/p>\n\n\n\n

Table of Contents<\/h5>\n\n\n\n

1. Definition<\/a><\/p>\n\n\n\n

2. Encoding<\/a><\/p>\n\n\n\n

3. Identical Solutions but Different Chromosomes<\/a><\/p>\n\n\n\n

4. Initialization<\/a><\/p>\n\n\n\n

5. Crossover<\/a><\/p>\n\n\n\n

6. Mutation<\/a><\/p>\n\n\n\n

7. Inversion<\/a><\/p>\n\n\n\n

8. Related<\/a><\/p>\n\n\n\n

References<\/a><\/p>\n\n\n\n

1. Definition\u2191<\/a><\/h5>\n\n\n\n

The Grouping Genetic Algorithms (GGA) were developed by\u00a0Falkenauer\u00a0[1<\/a>]\u00a0to solve clustering problems. In fact, GGA are a genetic framework for grouping problems, i.e. each particular problem needs its own customization. As the name suggests, GGA are an extension of the conventional Genetic Algorithms adapted to grouping problems.<\/p>\n\n\n\n

2. Encoding\u2191<\/a><\/h5>\n\n\n\n

There are other applications of Genetic Algorithms to solve grouping problems, but what makes GGA a well-designed solution is the coding used by\u00a0Falkenauer. To illustrate the encoding scheme used in GGA, let us consider the example in Figure\u00a01\u00a0where letters represent the groups and the numbers represent the objects.<\/p>\n\n\n\n

\"\"<\/p>\n\n\n\n

Figure 1. Example of solutions.<\/p>\n\n\n\n

Most\u00a0Genetic Algorithms (GA)<\/a>\u00a0dealing with grouping problems will choose the objects assignation as the information to store in a gene. Such chromosomes could be written:<\/p>\n\n\n\n

\\begin{array}{cccccccccc} C_{1} & = & F & C & E & E & C & F & E & F\\\\ C_{2} & = & D & H & A & D & A & D & H & H \\end{array}<\/p>\n\n\n\n

For\u00a0\\(C_1\\)<\/mathml>, the first object is assigned to group\u00a0\\(F\\), the second object to group\u00a0\\(C\\), the third and the fourth objects to group\u00a0\\(E\\)\u00a0and so on. Each group is different, which explains why other letters are used for both chromosomes. Assuming that a conventional crossover with the crossing site take at\u00a0\\(3\\)\u00a0is applied, the resulting chromosomes will be:<\/p>\n\n\n\n

\\begin{array}{ccccccccccc} C_{1}\\mid C_{2} & = & F & C & E & \\mid & D & A & D & H & H\\\\ C_{2}\\mid C_{1} & = & D & H & A & \\mid & E & C & F & E & F \\end{array}<\/p>\n\n\n\n

It is evident that these newly created chromosomes have no sense. Moreover, if some constraints on the groups exist, the resulting chromosomes will certainly contain many illegal groups.<\/p>\n\n\n\n

In GGA, the chromosomes are enhanced with a group element containing the group composition:<\/p>\n\n\n\n

\\begin{array}{cccccccccccccc} C_{1} & = & F & C & E & E & C & F & E & F & : & F & C & E\\\\ C_{2} & = & D & H & A & D & A & D & H & H & : & D & H & A \\end{array}<\/p>\n\n\n\n

All the operators work on the group element of the chromosomes. This coding respects the spirit of the \u201cbuilding blocs\u201d because GGA always manipulate groups. This coding has however a technical consequence, namely that the different chromosomes in the same population have different lengths.<\/p>\n\n\n\n

3. Identical Solutions but Different Chromosomes\u2191<\/a><\/h5>\n\n\n\n

One of the problems associated with the coding of grouping problems, is the fact that \u201cidentical solutions\u201d can be coded with different chromosomes. Figure\u00a02\u00a0illustrates this; the solutions are identical but, they are coded differently. The fact that the \u201csame\u201d groups have different letters is because the chromosomes were constructed independently so a chromosome cannot know that such a group already exists in another chromosome.<\/p>\n\n\n\n

\"\"<\/p>\n\n\n\n

Figure 2. Problem of identical solutions.<\/p>\n\n\n\n

A simple method can be used to identify these identical solutions. The idea is to construct a new object element like that of the chromosome, but using numbers for the groups rather than letters. The first object is always considered to be in group \\(1\\). If the second object is in a different group from the first one, it is put into group \\(2\\). Let us apply this method to the object element given by:<\/p>\n\n\n\n

\\[\\left.\\begin{array}{cccccccc} F & C & E & E & C & F & E & F\\end{array}\\right.\\rightarrow\\left.\\begin{array}{cccccccc} 1 & 2 & 3 & 3 & 2 & 1 & 2 & 1\\end{array}\\right.\\]\n\n\n\n

The first object is in group\u00a0\\(1=F\\). The second object has been put into group\u00a0\\(2=C\\)\u00a0because it is not grouped with the first object. The third object is put into group\u00a0\\(3=E\\)\u00a0because it is not grouped with the first or the second object. The fourth object is put into the same group\u00a0\\(3\\)\u00a0as the third one. The other objects are handled identically.<\/p>\n\n\n\n

When the same method is employed with the second chromosome, the new object element becomes:<\/p>\n\n\n\n

\\[\\left.\\begin{array}{cccccccc} H & A & D & D & A & H & D & H\\end{array}\\right.\\rightarrow\\left.\\begin{array}{cccccccc} 1 & 2 & 3 & 3 & 2 & 1 & 2 & 1\\end{array}\\right.\\]\n\n\n\n

The two newly created objects elements are identical, i.e. the groups are identical. When GGA identifies the same solution on numerous occasions in the same population, it decides to keep only one chromosome coding this solution. All the other chromosomes are modified by means of a special operator,\u00a0modify.<\/em>\u00a0This operator generally can just consist in the mutation of the corresponding chromosome.<\/p>\n\n\n\n

4. Initialization\u2191<\/a><\/h5>\n\n\n\n

Once the coding has been defined, the Grouping Genetic Algorithms must initialize the population. The method used depends on the particular problem because the different solutions must satisfy the hard constraints. Because GGA are meta-heuristic, heuristics are used most of the time to initialize the population. For example,\u00a0Falkenauer\u00a0suggests a first-fit heuristic for the bin packing problem.<\/p>\n\n\n\n

An important point concerning GGA is the diversity of the population, i.e. the heuristic must be adapted to produce different solutions each time it is called upon. If the objects are treated in random order in the case of the first-fit heuristic, the diversity of the population will be saved. Some heuristics cannot therefore be used for the initialization. In the bin packing problem the first-fit descending heuristic, where the objects are processed in descending order of size, is not used for initialization because if all the objects have different sizes, the heuristic will always produce the same solution and construct a population with identical chromosomes. This is of no particular interest.<\/p>\n\n\n\n

5. Crossover\u2191<\/a><\/h5>\n\n\n\n

Crossover is one of the most important operators in genetic algorithms. The crossover paradigm used for the Grouping Genetic Algorithms is shown in Figure\u00a03.<\/p>\n\n\n\n

\"\"<\/p>\n\n\n\n

Figure 3. GGA Crossover.<\/p>\n\n\n\n

The crossover consists of four steps:<\/p>\n\n\n\n

    \n
  1. A crossing site is chosen in each parent.<\/li>\n\n\n\n
  2. The bins selected by the crossing site of one parent are inserted at the crossing site of the second parent. At this stage, some objects may appear in more than one bin.<\/li>\n\n\n\n
  3. The existing bins containing objects that are already in the inserted bins are eliminated, i.e. some objects are no longer in a bin. If some bins are empty, they are also removed from the solution.<\/li>\n\n\n\n
  4. The objects left aside are reinserted into the solution.<\/li>\n<\/ol>\n\n\n\n

    With two parents it is possible to create two children by inserting the selected bins of the first parent into the second one, and by doing the reverse.<\/p>\n\n\n\n

    Concerning this latter step, a method must be used for the insertion. This method in fact depends on the problem to be solved because the operator must construct some valid solutions.\u00a0Falkenauersuggests a first-fit descending heuristic for example for the bin packing problem.<\/p>\n\n\n\n

    6. Mutation\u2191<\/a><\/h5>\n\n\n\n

    The role of a mutation operator is to insert new characteristics into a population to enhance the search space of the Genetic Algorithm. In the case of the Grouping Genetic Algorithms, the operator proposed is illustrated in Figure\u00a04.<\/p>\n\n\n\n

    \"\"<\/p>\n\n\n\n

    Figure 4. GGA Mutation.<\/p>\n\n\n\n

    The idea is to randomly choose a few bins and to remove them from the solution. The objects attached to these bins are then reinserted into the solution. The method used for the insertion of the objects is generally the same as the one used for the crossover operator.<\/p>\n\n\n\n

    7. Inversion\u2191<\/a><\/h5>\n\n\n\n

    The role of the inversion operator is to propose the same solution to the Grouping Genetic Algorithm, but differently. As pointed out in\u00a0section 3<\/a>, a single solution may have different presentations, and because crossovers work through crossing sites, the way in which a solution is presented influences the crossover operator\u2019s results. The first group appearing in the group element of a chromosome is likely less probability to be chosen than the other groups. It is therefore important to include this operator in the Grouping Genetic Algorithms. Figure\u00a05\u00a0gives the philosophy behind the inversion.<\/p>\n\n\n\n

    \"\"<\/p>\n\n\n\n

    Figure 5. GGA Inversion.<\/p>\n\n\n\n

    Two groups are randomly selected and their positions are switched in the solution. In the example, when the crossing site selected is between the second and third positions, the bins inserted will be \\(A\\) and \\(C\\) in the first solution and \\(D\\) and \\(C\\) in the second.<\/p>\n\n\n\n

    8. Related\u2191<\/a><\/h5>\n\n\n\n

    Similarity-based Grouping Genetic Algorithm<\/a><\/p>\n\n\n\n

    Nearest Neighbors Grouping Genetic Algorithm<\/a><\/p>\n\n\n\n

    References\u2191<\/a><\/h5>\n\n\n\n

    [1]\u00a0Emanuel Falkenauer,\u00a0Genetic Algorithms and Grouping Problems<\/em>, John Wiley, 1998.<\/p>\n","protected":false},"excerpt":{"rendered":"

    Abstract The Grouping Genetic Algorithms (GGA) are a kind of\u00a0Genetic Algorithms (GA)\u00a0applicable to solve grouping problems. Table of Contents 1. Definition 2. Encoding 3. Identical Solutions but Different Chromosomes 4. Initialization 5. Crossover 6. Mutation 7. Inversion 8. Related References 1. Definition\u2191 The Grouping Genetic Algorithms (GGA) were developed by\u00a0Falkenauer\u00a0[1]\u00a0to solve clustering problems. In fact, […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-2069","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/pages\/2069","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/comments?post=2069"}],"version-history":[{"count":9,"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/pages\/2069\/revisions"}],"predecessor-version":[{"id":2232,"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/pages\/2069\/revisions\/2232"}],"wp:attachment":[{"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/media?parent=2069"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}