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. Heuristics<\/a><\/p>\n\n\n\n 4.1. Select Object to Place<\/a><\/p>\n\n\n\n 4.2. Local Optimization<\/a><\/p>\n\n\n\n 4.3. Bottom-Left Heuristic<\/a><\/p>\n\n\n\n 4.4. Edge Heuristic<\/a><\/p>\n\n\n\n 4.5. The Center Heuristic<\/a><\/p>\n\n\n\n 4.6. Free Space Problem<\/a><\/p>\n\n\n\n 5. Initialization<\/a><\/p>\n\n\n\n 6. Crossover<\/a><\/p>\n\n\n\n 6.1. Object Selection<\/a><\/p>\n\n\n\n 6.2. Child Construction<\/a><\/p>\n\n\n\n 7. Mutation<\/a><\/p>\n\n\n\n 8. Inversion<\/a><\/p>\n\n\n\n 9. Validation<\/a><\/p>\n\n\n\n References<\/a><\/p>\n\n\n\n Notes<\/a><\/p>\n\n\n\n The 2D Genetic Algorithms (2D-GA) were developed to solve placement problems. In fact, 2D-GA are a genetic framework for placement problems, i.e. each particular problem needs its own customization. As the name suggests, 2D-GA are an extension of the conventional\u00a0Genetic Algorithms.<\/p>\n\n\n\n Remember that for the\u00a0placement problems<\/a>, each object may have multiple valid orientations. The solution consists of a position for each object with a given valid orientation. Figure 1\u00a0proposes two solutions,\u00a0 Figure 1. Two solutions for a placement problem.<\/p>\n\n\n\n In the 2D-GA, the chromosomes store for the different object of a solution their position and the particular orientation used for the placement. Figure\u00a01\u00a0shows two examples for which the corresponding chromosomes are:<\/p>\n\n\n\n \\[C_{1}={(0,0,Normal),(10,0,Normal),(20,0,Normal),(0,10,Normal)(10,10,Normal)}\\]\n\n\n\n \\[C_{2}={(10,0,Normal),(10,10,Normal),(0,20,Normal),(20,20,Normal)(0,0,Rota90)}\\]\n\n\n\n A genetic algorithm needs to evaluate the chromosomes of a population. For the 2D-GA, the performance of a particular chromosome (placement) is determined by two criteria that are difficult to compare:<\/p>\n\n\n\n The evaluation of a given placement is thus a multi-criteria problem, and we decide to use the\u00a0multiple objective approach<\/a>\u00a0based on the\u00a0PROMETHEE method<\/a>. Actually, the two criteria have the same characteristics and are both to be minimized:<\/p>\n\n\n\n It is possible to change the values of the PROMETHEE parameters for a specific problem1<\/a><\/sup>.<\/p>\n\n\n\n Because GA are meta-heuristic, heuristics are central in the 2D-GA. Three different heuristics were developed based on a same generic approach described by Algorithm\u00a01<\/a>.<\/p>\n\n\n\n Require:<\/p>\n\n\n\n Objects to place,\u00a0\\(O\\)<\/p>\n\n\n\n <\/p>\n\n\n\n Build a random array of not placed objects,\u00a0\\(O\\)<\/p>\n\n\n\n while (\\(\u2203o_i\u2208O\\)):<\/p>\n\n\n\n \\(o_i\u2190MostConnected(O)\\)<\/p>\n\n\n\n \\((x,y)\u2190IsFreeSpace(o_i)\\)<\/p>\n\n\n\n if\u00a0\\((x,y)\\) are not valid:<\/p>\n\n\n\n \\((x,y)\u2190PlaceRect(oi)LocalOptimization(o_i)\\)<\/p>\n\n\n\n \\(UpdateFreeSpace()\\)<\/p>\n\n\n\n Algorithm 1. Generic placement heuristic.<\/p>\n\n\n\n For all the objects to place, the heuristic selects iteratively the most connected one (section\u00a04.1<\/a>) and look if an existing free space can hold it. If no, a method place the object, and a local optimization is performed (section\u00a04.2<\/a>). Finally, the free spaces are updated. Sections\u00a04.3<\/a>,\u00a04.4<\/a>\u00a0and\u00a04.5<\/a>\u00a0presents three strategies to place an object. Section\u00a04.6<\/a>\u00a0explains the free space problem.<\/p>\n\n\n\n When choosing a object to place, each heuristic parses the random array of object\u00a0\\(O\\). For each object, the heuristic computes the sum of the weights of the connections involving it and which are composed from at least one already placed object.<\/p>\n\n\n\n This method ensures that the most connected objects are placed first, while the randomization of the array of objects to place should provide diversity in the population.<\/p>\n\n\n\n To increase the speed of the implemented heuristics, the objects are first considered as rectangles (the bounding rectangles of the corresponding polygons). Once the rectangle is placed, the position must be adapted by transforming it into the original polygon. This is the role of the local optimization. Figure 2 shows two examples, where the object\u00a0\\(2\\)\u00a0is first placed as a rectangle.<\/p>\n\n\n Figure 2. The local optimization.<\/p>\n\n\n\n In the first example (a), the object must be placed as close as possible from the \u201cbottom-left\u201d corner, while in the second example (b), it must be placed as close as possible from the point represented by the intersection of the dashed lines.<\/p>\n\n\n\n The bottom-left heuristic is a very simple method. The basic principle is to place the first object in the bottom-left corner. The next objects are placed next to it at the right until the horizontal limit is exceeded. After that, the heuristic creates a \u201cnew line\u201d, i.e. starts for the next objects again from the left limit and at a given height determined by the highest object already placed. Figure\u00a03\u00a0shows an example of this heuristic (the numbers indicate the order in which the objects were placed).<\/p>\n\n\n Figure 3. The bottom-left heuristic.<\/p>\n\n\n\n While this heuristic is very simple, efficient and fast, it has a big drawback: the bounding rectangle will have a length close to the one of the horizontal limit, but the height can be much smaller than the vertical limit. For some problems where the resulting rectangle has to be \u201cbalanced\u201d, this heuristic does not provide good results. Another problem is that two consecutively placed objects, which are connected together, are not necessary place close from each other (objects\u00a0\\(7\\)\u00a0and\u00a0\\(8\\)\u00a0of Figure\u00a03), this is also a disadvantage for the \u201cdistance\u201d criterion.<\/p>\n\n\n\n The edge heuristic is derived from the bottom-left, with the aim to obtain a bounding rectangle whose dimensions are proportional to the limits of the problem. The first object is also put in the bottom-left corner, but for the second object, the heuristic determines two different positions: at the right of the first object or above it. For these positions, the heuristic computes the rate\u00a0heightlength\u00a0to determine the position which gives the closest rate to the corresponding one of the limiting height and length. The next objects are treated in the same way. Figure\u00a04 shows an example of this heuristic (the numbers indicate the order in which the objects were placed).<\/p>\n\n\n Figure 4. The edge heuristic.<\/p>\n\n\n\n With this heuristic, the problem of the bounding rectangle of the bottom-left heuristic is solved. The price to pay is that the total area of the bounding rectangle is larger than the one obtain with the bottom-left heuristic. It works a little bit slower than the bottom-left heuristic. It also has the same problem than the bottom-left heuristic one in regards of the \u201cdistance\u201d criterion, because again two consecutive objects can be placed far from each other.<\/p>\n\n\n\n To avoid the problem of the \u201cdistance\u201d criterion, the center heuristic was developed. The idea is to place the objects as close as possible from the center. Of course, when the number of objects already placed increases, the number of possible positions for the next object also increases. The result is that this method is really slower than the other two. Figure\u00a05\u00a0shows an example of this approach (the numbers indicate the order in which the objects were placed).<\/p>\n\n\n Figure 5. The center heuristic.<\/p>\n\n\n\n This heuristic gives the best results in terms of \u201cdistance\u201d criterion while it still give performing solutions in terms of \u201carea\u201d criterion.<\/p>\n\n\n\n One of the problem which appears when placing objects, in particular if they are polygons, is the formation of \u201cfree spaces\u201d, i.e. regions without objects completely enclosed by objects and that could not be used directly by the heuristics. Figure\u00a06 shows an example (the numbers represent again the order in which the objects were placed).<\/p>\n\n\n Figure 6. The free space problem.<\/p>\n\n\n\n When the object\u00a0\\(4\\)\u00a0is placed, it automatically creates a \u201cfree space\u201d, a region colored in gray. It is also evident that the object\u00a0\\(5\\)\u00a0can be placed in this \u201cfree space\u201d. This is why a method was developed to compute the polygons corresponding to these \u201cfree spaces\u201d after each positioning. Before the algorithm determines possible positions according the heuristic strategy, it looks whether there is a \u201cfree space\u201d that can hold this element.<\/p>\n\n\n\n The problem of finding a good \u201cfree space\u201d for a given element is close to the \u201cdynamic storage allocation\u201d problem. When a program is asking for a given quantity of memory, the operating system must choose between the free regions in RAM, which one to be used for the given bloc, in order to limit the fragmentation of the memory (Figure 7).\u00a0<\/p>\n\n\n Figure 7. The dynamic storage allocation.<\/p>\n\n\n\n There are several algorithms to solve this problem\u00a0[1<\/a>]:<\/p>\n\n\n\n These methods were compared, in particular in\u00a0[2<\/a>]\u00a0and\u00a0[3<\/a>], where it was demonstrated that the first-fit and best-fit strategies are better than the worst-fit. For many years, the best-fit was applied because it preserves the larger free regions for future demands of big quantities of memory. On the other hand, it increases the number of very few regions that will never hold a bloc. In fact, the first-fit and best-fit strategies give, in terms of memory fragmentation, the same kind of quality. That is the reason why, the first-fit is used because it is faster than the best-fit where all the free region have to be controlled.<\/p>\n\n\n\n In the case of the \u201cfree spaces\u201d treatment, a first-fit strategy was implemented: the first \u201cfree space\u201d that can hold a given element is chosen.<\/p>\n\n\n\n Once the coding has been defined, the 2D-GA must initialize the population. The method used depends on the particular problem because the different solutions must satisfy the hard constraints. In practice, a heuristic should be defined to place a given set of objects.<\/p>\n\n\n\n The role of the crossover is to construct a new solution called a child by taking \u201cgood\u201d portions of two solutions called the parents. In the case of placement problems, an intuitive crossover is to select a portion of the placement of both parents as the basis to construct the children.<\/p>\n\n\n Figure 8. The crossover operator for the 2D-GA.<\/p>\n\n\n\n An example is showed at Figure\u00a08. From each parent, a set of objects are chosen (filled in gray on the figure), one child is further constructed by using these sets.<\/p>\n\n\n\n The crossover depends of course of the choice of the objects to be inherited from the parents. A good set of objects is characterized by two criteria:<\/p>\n\n\n\n The selector first classify all the objects by \u201cwell connected\u201d. To define a \u201cwell connected\u201d object, we reach two criteria:<\/p>\n\n\n\n This is a multi-criteria problem, and the\u00a0PROMETHEE method<\/a>\u00a0is used to solve it. The two criteria have the same characteristics:<\/p>\n\n\n\n Of course, the \u201cweight criterion\u201d has to be maximized and the \u201cdistance criterion\u201d has to be minimized2<\/a><\/sup>.\u00a0<\/p>\n\n\n\n The selector chooses the \u201cbest connected\u201d object not already selected\u200a2<\/a><\/sup>. After that, the selector looks which is the second \u201cbest connected\u201d object not already selected so that the two objects can be contained in the \u201cchoice rectangle\u201d whose size is the quarter of the total occupied space by all the objects. The set of selected objects is filled with these two objects, and all the other objects that are inside the \u201cchoice rectangle\u201d.<\/p>\n\n\n\n An example is showed at Figure\u00a09, where object\u00a0\\(1\\)\u00a0is the \u201cbest connected\u201d and object\u00a0\\(2\\)\u00a0is the second \u201cbest connected\u201d, and the \u201cchoice rectangle\u201d is drawn as dashed. The selected objects are those in gray.<\/p>\n\n\n Figure 9. The object selection.<\/p>\n\n\n\n To construct a child, the operator considers that the sets of objects of the two parents are a sort of super blocs that can be treated by the heuristics as single objects. Then a heuristic is used to place these two objects and all the others that are not selected in one of the parent sets.\u00a0<\/p>\n\n\n\n The strategy of the mutation currently implemented is to create a totally new chromosome by using a heuristics.<\/p>\n\n\n\n Of course, this strategy limits the advantages of the way the mutation choose the chromosomes, that is the reason why developing a new mutation strategy will be one of the priorities in the future developments.<\/p>\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 2D-GA, 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 A first prototype was developed during a research project aimed to develop a method of helping to create Very-Large-Scale Integration (VLSI) chips, and funded by the Walloon Region from 1999 to 2001. Furthermore, because not enough tests have being done actually, it is only possible to present qualitative results rather than quantitative ones.<\/p>\n\n\n\n For the VLSI problem, where the connections are a very important aspect, the best placement strategy is the center heuristic, because it guarantees that two objects treated consecutively will be placed closed from each other. Furthermore, if the external connectors are disposed around the limiting area, the objects can be place at \u201cequal\u201d distance from each border. An example is showed at Figure\u00a010. With the bottom-left and edge heuristics, all the elements placed will be translated to the bottom-left corner (Position\u00a0\\(O\\)), which implies an amelioration for the net\u00a0\\(a\\), but a deterioration for all other nets represented.<\/p>\n\n\n Figure 10. Advantages of the \u201ccenter\u201d heuristic.<\/p>\n\n\n\n For the crossover, a problem occurs when there are some large blocs in comparison to the limiting area. An example is showed at Figure\u00a011, where the two best objects (\\(1\\)\u00a0and\u00a0\\(2\\)), selected during the crossover, define a rectangle that holds only a single object. In this case, no interesting information are shared, because the crossover is reduced to run the initial heuristic. This problem becomes important when there are only a few \u201cbig\u201d objects to place.<\/p>\n\n\n Figure 11. Problem for the element selection in the crossover operator.<\/p>\n\n\n\n [1]\u00a0Donald E. Knuth,\u00a0The Art of Computer Programming, Vol. 1: Fundamental Algorithms<\/em>, 2\u1d49 ed., Addison-Wesley, 1998.\u00a0<\/p>\n\n\n\n [2]\u00a0Carter Bays, \u201cA Comparaison of Next-Fit, First-Fit, and Best-Fit\u201d,\u00a0Communications of the ACM<\/em>, 20(3), pp. 191\u2014192, 1977.<\/p>\n\n\n\n [3]\u00a0John E. Shore, \u201cOn the External Fragmentation Produced by First-Fit and Best-Fit Allocation Strategies\u201d,\u00a0Communications of the ACM<\/em>, 18(8), pp. 443\u2014440,1975.<\/p>\n\n\n\n Abstract The 2D Genetic Algorithms (2DGA) are a kind of\u00a0Genetic Algorithms (GA)\u00a0applicable to solve\u00a0placement problems. Table of Contents 1. Definition 2. Encoding 3. Evaluation 4. Heuristics 4.1. Select Object to Place 4.2. Local Optimization 4.3. Bottom-Left Heuristic 4.4. Edge Heuristic 4.5. The Center Heuristic 4.6. Free Space Problem 5. Initialization 6. Crossover 6.1. Object Selection […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":"[{\"content\":\"It is also possible to change the value during the evolution process, but there are actually no reasons to implement something like this.\",\"id\":\"0de2fa1a-be91-4e11-8e7a-5e220d6ddd21\"},{\"content\":\"It is possible to change the values of the PROMETHEE parameters for a specific problem.\",\"id\":\"864f1200-9de0-4a9a-8b49-fda4144f88bf\"},{\"content\":\"In fact, the same object cannot be selected in both parent, i.e. when an object is chosen in one parent, it cannot be chosen in the second parent.\",\"id\":\"d45bd830-264e-49bf-98cd-566a97c0a185\"}]"},"class_list":["post-1719","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/pages\/1719","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=1719"}],"version-history":[{"count":47,"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/pages\/1719\/revisions"}],"predecessor-version":[{"id":2220,"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/pages\/1719\/revisions\/2220"}],"wp:attachment":[{"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/media?parent=1719"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}1. Definition\u2191<\/a><\/h5>\n\n\n\n
2. Encoding\u2191<\/a><\/h5>\n\n\n\n
![\"\"](\"http:\/\/xeddixx.cluster029.hosting.ovh.net\/wp-content\/uploads\/2025\/10\/2dencoding.png\")
<\/figure>\n<\/div>\n\n\n3. Evaluation\u2191<\/a><\/h5>\n\n\n\n
\n
\n
4. Heuristics\u2191<\/a><\/h5>\n\n\n\n
4.1. Select Object to Place\u2191<\/a><\/h6>\n\n\n\n
4.2. Local Optimization\u2191<\/a><\/h6>\n\n\n\n
![\"\"](\"http:\/\/xeddixx.cluster029.hosting.ovh.net\/wp-content\/uploads\/2025\/10\/2dheuropti.png\")
<\/figure>\n<\/div>\n\n\n4.3. Bottom-Left Heuristic\u2191<\/a><\/h6>\n\n\n\n
![\"\"](\"http:\/\/xeddixx.cluster029.hosting.ovh.net\/wp-content\/uploads\/2025\/10\/2dbottomleft.png\")
<\/figure>\n<\/div>\n\n\n4.4. Edge Heuristic\u2191<\/a><\/h6>\n\n\n\n
![\"\"](\"http:\/\/xeddixx.cluster029.hosting.ovh.net\/wp-content\/uploads\/2025\/10\/2dedge.png\")
<\/figure>\n<\/div>\n\n\n4.5. The Center Heuristic\u2191<\/a><\/h6>\n\n\n\n
![\"\"](\"http:\/\/xeddixx.cluster029.hosting.ovh.net\/wp-content\/uploads\/2025\/10\/2dcenter.png\")
<\/figure>\n<\/div>\n\n\n4.6. Free Space Problem\u2191<\/a><\/h6>\n\n\n\n
![\"\"](\"http:\/\/xeddixx.cluster029.hosting.ovh.net\/wp-content\/uploads\/2025\/10\/2dspaces.png\")
<\/figure>\n<\/div>\n\n\n![\"\"](\"http:\/\/xeddixx.cluster029.hosting.ovh.net\/wp-content\/uploads\/2025\/10\/2dmemprob.png\")
<\/figure>\n<\/div>\n\n\n\n
5. Initialization\u2191<\/a><\/h5>\n\n\n\n
6. Crossover\u2191<\/a><\/h5>\n\n\n\n
![\"\"](\"http:\/\/xeddixx.cluster029.hosting.ovh.net\/wp-content\/uploads\/2025\/10\/2dcross.png\")
<\/figure>\n<\/div>\n\n\n6.1. Object Selection\u2191<\/a><\/h6>\n\n\n\n
\n
\n
\n
![\"\"](\"http:\/\/xeddixx.cluster029.hosting.ovh.net\/wp-content\/uploads\/2025\/10\/2dcrosselect.png\")
<\/figure>\n<\/div>\n\n\n6.2. Child Construction\u2191<\/a><\/h6>\n\n\n\n
7. Mutation\u2191<\/a><\/h5>\n\n\n\n
8. Inversion\u2191<\/a><\/h5>\n\n\n\n
9. Validation\u2191<\/a><\/h5>\n\n\n\n
![\"\"](\"http:\/\/xeddixx.cluster029.hosting.ovh.net\/wp-content\/uploads\/2025\/10\/vlsiheuristic.png\")
<\/figure>\n<\/div>\n\n\n![\"\"](\"http:\/\/xeddixx.cluster029.hosting.ovh.net\/wp-content\/uploads\/2025\/10\/vlsiexplac.png\")
<\/figure>\n<\/div>\n\n\nReferences\u2191<\/a><\/h5>\n\n\n\n
Notes\u2191<\/a><\/h5>\n\n\n