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

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

The Hierarchical Genetic Algorithms (HGA) are a kind of\u00a0Genetic Algorithms (GA)<\/a>\u00a0applicable to solve\u00a0hierarchical problems<\/a>.<\/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. Evaluation<\/a><\/p>\n\n\n\n

4. Heuristic<\/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

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

The Hierarchical Genetic Algorithms (HGA) were developed to solve a particular class of hierarchical problems: the\u00a0tree to build refers to the set theory<\/a>. In fact, HGA are a genetic framework for placement problems, i.e. each particular problem needs its own customization. As the name suggests, HGA are an extension of the conventional\u00a0Genetic Algorithms<\/a>.<\/p>\n\n\n\n

Starting from a set of objects,\u00a0\\(O=\\{o_{i}\\}\\)<\/mathml>, each object being described by a set a features, the HGA build a hierarchy of nodes where these objects are assigned in order to optimize a given cost function. An example is the\u00a0building of taxonomy<\/a>\u00a0based on concepts extracted from a document corpus.<\/p>\n\n\n\n

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

In the HGA, the chromosomes represents a given tree. The coding scheme includes a\u00a0node element<\/em>\u00a0and an\u00a0object element<\/em>. In practice, each chromosomes is represented by:<\/p>\n\n\n\n

    \n
  1. An array of nodes, each node containing the index of the first child node and the number of its child node.<\/li>\n\n\n\n
  2. An array holds the assignation of each object.<\/li>\n<\/ol>\n\n\n\n

    Figure 1\u00a0proposes an example of a tree defining \\(6\\) nodes of \\(9\\) objects.<\/p>\n\n\n\n

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

    Figure 1. Example of a tree.<\/p>\n\n\n\n

    The corresponding chromosome is presented at Figure\u00a02. The \u201cleft part\u201d of the chromosome represents the description of the hierarchy of nodes. The array begins with the two top nodes (\\(n_1\\)\u00a0and\u00a0\\(n_3\\)). Each class is described as a pair of\u00a0(index,length). For example,\u00a0\\(n_1\\)\u00a0is defined by\u00a0\\((2,2)\\)\u00a0since the index of the first sub-node (\\(n_2\\)) is \\(1\\) and it has two child nodes (\\(n_2\\)\u00a0and\u00a0\\(n_4\\)). The \u201cright part\u201d of the chromosome represents the assignment of the different object. For example, object\u00a0\\(o_5\\) is assigned to\u00a0\\(n_6\\).<\/p>\n\n\n\n

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

    Figure 2. Example of a chromosome.<\/p>\n\n\n\n

    3. Evaluation\u2191<\/a><\/h5>\n\n\n\n

    The evaluation of the chromosomes is an important feature of a genetic algorithm. Since the goal is to obtain a balanced tree, an idea is to minimize the average length of the path to reach each object.<\/p>\n\n\n\n

    To compute the length of a given path, I propose to sum the depth of the path (the number of nodes to traverse) with the number of choices at each intermediate node. Let us define\u00a0\\(n_{n}(j)\\) as the number of child nodes of\u00a0\\(n_j\\)\u00a0(\\(n_{n}(root)\\)\u00a0is the number of top nodes) and\u00a0\\(n_{o}(j)\\)\u00a0as the number of objects assigned to node\u00a0\\(n_j\\). Moreover, let us define a cost,\u00a0\\(cost(n_{j})\\), for each node,\u00a0\\(n_j\\):<\/p>\n\n\n\n

    \\[cost(n_{j})=\\left\\{ \\begin{array}{lc} n_{n}(root) & Parent(n_{j})=root\\\\ cost(Parent(n_{j}))+n_{n}(Parent(n_{j}))+n_{o}(Parent(n_{j})) & Parent(n_{j})\\neq root \\end{array}\\right.\\]\n\n\n\n

    where\u00a0\\(Parent(n_{j})\\)\u00a0is a function returning the parent node of\u00a0\\(n_j\\)\u00a0and\u00a0\\(root\\)\u00a0is the root node.<\/p>\n\n\n\n

    The cost function,\u00a0\\(cost\\), to minimize is defined as:<\/p>\n\n\n\n

    \\[cost=\\frac{1}{|\\mathcal{O}|}\\sum_{i}cost(Assign(o_{i}))\\]\n\n\n\n

    where\u00a0\\(Assign(o_{i})\\)\u00a0is a function returning the node where object\u00a0\\(o_i\\)\u00a0is assigned. Figures\u00a03\u00a0and\u00a04\u00a0show two tree examples. When comparing\u00a0\\(T_1\\)\u00a0and\u00a0\\(T_2\\), it seems clear that\u00a0\\(T_2\\)\u00a0is more unbalanced than\u00a0\\(T_1\\).<\/p>\n\n\n\n

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

    Figure 3. Tree\u00a0T1.<\/p>\n\n\n\n

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

    Figure 4. Tree\u00a0T2.<\/p>\n\n\n\n

    Let us compute the cost function for these trees:<\/p>\n\n\n\n

    \\begin{align}cost(T_{1})&=&\\frac{6+6+9+9+5+5+5}{7}=6.43\\\\cost(T_{2})&=&\\frac{8+8+9+9+9+5+5}{7}=7.57\\end{align}<\/p>\n\n\n\n

    As expected,\u00a0\\(cost(T_{2})>cost(T_{1})\\).<\/p>\n\n\n\n

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

    Since the GA are meta-heuristics, the heuristics play an important role and must be adapted for the particularity of the problem. This section presents the heuristic used by the HGA. Algorithm\u00a01\u00a0shows the generic idea : the objects are randomly selected and a node in the tree is searched that can hold the current object.<\/p>\n\n\n\n

    Require:\u00a0<\/p>\n\n\n\n

    \u00a0\u00a0\u00a0Tree\u00a0\\(T\\)<\/p>\n\n\n\n

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

    Build a random array of unassigned objects of\u00a0\\(T\\),\u00a0\\(\\mathcal{O}\\)
    for (\\(\\forall o_{i}\\in\\mathcal{O}\\)):<\/p>\n\n\n\n

    \\(New\\leftarrow Find(T,o_{i})\\)<\/p>\n\n\n\n

    \\(T.Attach(New,o_{i})\\)<\/p>\n\n\n\n

    Algorithm 1. The heuristic,\u00a0Heuristc(T).<\/p>\n\n\n\n

    Algorithm\u00a02 describes the method that searches for a node that will hold an object (\\(Attr\\)\u00a0is a function returning the list of attributes of an object or a node). The basic idea is to find the \u201cfirst highest\u201d node that can hold a given object. The method parses each level in the hierarchy to find a node that can hold a given object. To be selected, a node must share at least one attribute with the object. Three situation may occur:<\/p>\n\n\n\n

      \n
    1. The node has exactly the same attributes as the object : The object will be attached to it.<\/li>\n\n\n\n
    2. All the attributes of the node are attributes of the object : The method looks further in the branch of the tree corresponding to it.<\/li>\n\n\n\n
    3. Some attributes of the node are attributes of the object : an intermediate node with the common attributes must be created.<\/li>\n<\/ol>\n\n\n\n

      Of course, if no node shares some attributes with the object, a new root node must be created.<\/p>\n\n\n\n

      Require:<\/p>\n\n\n\n

      \u00a0\u00a0\u00a0Object\u00a0\\(o\\)\u00a0to assigned and a tree\u00a0\\(T\\)<\/p>\n\n\n\n

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

      \\(Parent\\leftarrow0\\)\u00a0{Start at the root node}
      loop:<\/p>\n\n\n\n

      Build a random array containing all the child nodes of\u00a0\\(Parent\\),\u00a0\\(N\\)<\/p>\n\n\n\n

      \\(GoDeeper\\leftarrow\\mathrm{False}\\)<\/p>\n\n\n\n

      \\(None\\leftarrow0\\)<\/p>\n\n\n\n

      \\(NbMax\\leftarrow0\\)<\/p>\n\n\n\n

      for (\\(\\forall n_{i}\\in\\mathcal{N}\\)):<\/p>\n\n\n\n

      \\(Nb\\leftarrow|Attr(o)\\cup Attr(n_{i})|\\)<\/p>\n\n\n\n

      if (\\(Nb=0\\)):<\/p>\n\n\n\n

      continue<\/p>\n\n\n\n

      if (\\(Nb=|Attr(n_{i})|\\)): {Good branch was found}<\/p>\n\n\n\n

      if (\\(Nb=|Attr(o)|\\)):<\/p>\n\n\n\n

      return\u00a0ni<\/p>\n\n\n\n

      \\(Parent\\leftarrow n_{i}\\)<\/p>\n\n\n\n

      \\(GoDeeper\\leftarrow\\mathrm{True}\\)<\/p>\n\n\n\n

      break<\/p>\n\n\n\n

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

      if (\\(NbMax\n\n\n\n

      \\(NbMax\\leftarrow Nb\\)<\/p>\n\n\n\n

      \\(Node\\leftarrow n_{i}\\)<\/p>\n\n\n\n

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

      if (\\(GoDeeper=\\mathrm{True}\\)):<\/p>\n\n\n\n

      break<\/p>\n\n\n\n

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

      if (\\(Node=0\\)):<\/p>\n\n\n\n

      return\u00a0\\(T.NewNode(Attr(o),Parent)\\)<\/p>\n\n\n\n

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

      {\\(Node\\)\u00a0contains some attributes not representing the object.}<\/p>\n\n\n\n

      \\(Common=Attr(o)\\cup Attr(Node)\\)<\/p>\n\n\n\n

      if (\\(Parent\\) and \\(|Attr(Parent)|=|Common|\\)):<\/p>\n\n\n\n

      return\\(T.NewNode(Attr(o),Parent)\\)<\/p>\n\n\n\n

      \\(New\\leftarrow T.NewNode(Common,Parent)\\)\u00a0{Create a new node attached to\u00a0\\(Parent\\)}<\/p>\n\n\n\n

      \\(T.MoveNode(New,Node)\\)\u00a0{\\(New\\)\u00a0has\u00a0\\(Node\\)\u00a0as child}<\/p>\n\n\n\n

      return\u00a0\\(T.NewNode(Common,New)\\)\u00a0{\\(New\\)\u00a0has a new node containing the object}<\/p>\n\n\n\n

      Algorithm 2. Find a node for object\u00a0o,\u00a0Find(o,T).<\/p>\n\n\n\n

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

      The role of the crossover operator is to construct a new chromosome using two parents. If the operator mix \u201cgood patterns\u201d from both parents, the child chromosome should be a \u201cgood\u201d one.<\/p>\n\n\n\n


      The crossover proposed for the HGA combines the trees of both parent based on a\u00a0crossing site<\/em>\u00a0defined as two nodes (one in each parent) having the same attributes. It is then possible to replace the branch of one tree with the other.<\/p>\n\n\n\n

      In practice, the operator verifies that an object is not assigned twice and run the heuristic if there remains unassigned objects. Algorithm\u00a03 describes the crossover operator ((Objs)\u00a0is a function returning the list of objects attached to a node).<\/p>\n\n\n\n

      Require:\u00a0<\/p>\n\n\n\n

      \u00a0\u00a0\u00a0Two parent trees,\u00a0\\(T_1\\)\u00a0and\u00a0\\(T_2\\), and a child tree,\u00a0\\(C\\)<\/p>\n\n\n\n

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

      Build a random array containing all the nodes of\u00a0\\(T_1\\),\u00a0\\(\\mathcal{N}_{1}\\)
      Build a random array containing all the nodes of\u00a0\\(T_2\\),\u00a0\\(\\mathcal{N}_{2}\\)
      \\(Node_{1}\\leftarrow 0\\)
      \\(Node_{2}\\leftarrow 0\\)
      for (\\(\\forall n_{j}\\in\\mathcal{N}_{1}\\)):<\/p>\n\n\n\n

      for (\\(\\forall n_{k}\\in\\mathcal{N}_{2}\\)):<\/p>\n\n\n\n

      if (\\(Attr(n_{j})=Attr(n_{k})\\)):<\/p>\n\n\n\n

      \\(Node_{1}\\leftarrow n_{j}\\)<\/p>\n\n\n\n

      \\(Node_{2}\\leftarrow n_{k}\\)<\/p>\n\n\n\n

      break<\/p>\n\n\n\n

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

      if (\\(Node_{1}\\neq0\\)):<\/p>\n\n\n\n

      \\(Clear(C)\\)<\/p>\n\n\n\n

      \\(thObjs\\leftarrow Objs(Node_{2})\\)<\/p>\n\n\n\n

      \\(Node\\leftarrow C.CopyExceptBranchAndObjects(T_{1},Node_{1},thObjs)\\)<\/p>\n\n\n\n

      \\(New\\leftarrow C.ReserveNode()\\)<\/p>\n\n\n\n

      \\(C.Insert(Node,New)\\)<\/p>\n\n\n\n

      \\(C.CopyExceptBranch(Node_{2})\\)<\/p>\n\n\n\n

      \\(Heuristic(C)\\)<\/p>\n\n\n\n

      else:<\/p>\n\n\n\n

      print \u201cError: no crossing site\u201d<\/p>\n\n\n\n

      Algorithm 3. Crossover of the HGA<\/p>\n\n\n\n

      An important element is that, if a crossing site is not found (there are not two nodes with the same attributes from each tree), the crossover cannot be done.<\/p>\n\n\n\n

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

      Te role of the mutation operator is modify a given chromosome to explore new portions of the search space. Most of the time, it is implemented as a little modification of the chromosome. I apply this idea by choosing randomly a node and delete it, and using then the heuristic to attach the unassigned objects (Algorithm\u00a04).<\/p>\n\n\n\n

      Require:\u00a0<\/p>\n\n\n\n

      \u00a0\u00a0\u00a0Tree\u00a0\\(T\\)<\/p>\n\n\n\n

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

      Choose randomly a node,\u00a0\\(Node\\)
      \\(T.Delete(Node)\\)
      \\(Heuristic(T)\\)<\/p>\n\n\n\n

      Algorithm 4. Mutation of the HGA<\/p>\n\n\n\n

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

      The inversion, whose role consists in presenting differently a given chromosome without changing its corresponding information, is not implemented in the HGA, because all the operators are based on the \u201cinterpretation\u201d of the chromosomes rather than on the encoding of the chromosomes.\u00a0<\/p>\n\n\n\n

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

      Taxonomy Building<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

      Abstract The Hierarchical Genetic Algorithms (HGA) are a kind of\u00a0Genetic Algorithms (GA)\u00a0applicable to solve\u00a0hierarchical problems. Table of Contents 1. Definition 2. Encoding 3. Evaluation 4. Heuristic 5. Crossover 6. Mutation 7. Inversion 8. Related 1. Definition\u2191 The Hierarchical Genetic Algorithms (HGA) were developed to solve a particular class of hierarchical problems: the\u00a0tree to build refers […]<\/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-2083","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/pages\/2083","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=2083"}],"version-history":[{"count":22,"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/pages\/2083\/revisions"}],"predecessor-version":[{"id":2234,"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/pages\/2083\/revisions\/2234"}],"wp:attachment":[{"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/media?parent=2083"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}