Shulou(Shulou.com)06/01 Report--

Editor to share with you how to use Python map four-color principle of genetic algorithm coloring, I believe that most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's go to know it!

1 task requirements

   first, let's clarify the requirements that need to be implemented in this article.

   has a vector layer composed of multiple small patches, as shown in the following image; we need to find a color matching scheme composed of four colors, and shade the patches of the vector layer so that the colors of the adjacent small patches are inconsistent, as shown in the following image.

   here, we use the four-color theorem (Four Color Theorem), also known as the four-color map theorem (Four Color Map Theorem): if there are some contiguous finite areas on the plane, then at most four colors can be used to dye these different regions, so that every two adjacent regions can be dyed differently.

2 code implementation

When    defines the requirements, we can start writing specific code. At present, in the major blogs in China, there are a lot of codes about Python to realize map four-color principle coloring, most of which are based on backtracking method; while in an English blog page, we see the implementation of map four-color principle coloring based on genetic algorithm. Then take the code as an example to do the operation. Here, because my own understanding of genetic algorithm is not in-depth, so there are more or less deficiencies in the introduction of the code. I hope you will criticize and correct me.

2.1 basic ideas

   genetic algorithm is a search algorithm used to solve the optimization problem, which belongs to the category of evolutionary algorithm. Combined with the above requirements, first of all, the color of each region can be taken as a gene, and the individual genotype is the summary of color genes in all regions (78 small spots in the above-mentioned vector layer, that is, 78 regions). By constructing the Rule class, the "adjacent" in the spatial sense can be transformed into information that can be recognized by genetic algorithms (that is, individual genetic changes can be constrained). Then, combined with the replacement of offspring, the genome that meets the requirements is found; finally, the genome is converted into color information in the spatial sense, and the results are output.

The specific step-by-step ideas for    are as follows:

Define rules. Rules are used to convert the spatial connections between regions into information that can be recognized by genetic algorithms; the two regions connected by rules are adjacent in space. Define the functions required to check the connectivity of area spaces. These functions are used to check whether the connectivity between the two regions is logical; for example, if area An and area B are shown in the rules, then area B must also show the connection to area An in the rules. Define individual genotypes. Among them, each individual has 78 genes, each of which represents the color of a region. Individual replacement and optimal gene selection. Through the continuous change of individuals, the individual genotypes that meet the requirements of the rules are selected. Genotypic explanation. The interpretation of the obtained individual genotypes is equivalent to the inverse process of the first step, that is, converting genetic information into spatial connections. Results check. Check whether the color obtained is consistent with each gene in the genome of the optimal individual. 2.2 Code explanation

   next, I'll introduce the complete code. Where shapefile_path is the save path of the vector layer, and "POLY_ID_OG" is a field in the property sheet of the vector layer, which represents the number of each small speckle.

#-*-coding: utf-8-* "Created on Sun Oct 31 19:22:33 2021@author: Chutj"import geneticimport unittestimport datetimefrom libpysal.weights import Queenshapefile_path=" G:/Python_Home1/stl_hom_utm.shp "weights=Queen.from_shapefile (shapefile_path," POLY_ID_OG ") one_neighbor_other=weights.neighbors# defines" rules "to convert spatial connections between regions into information that can be recognized by genetic algorithms. The two regions connected by the Rule are adjacent class Rule in space: Item = None Other = None Stringified = None def _ init__ (self, item, other, stringified): self.Item = item self.Other = other self.Stringified = stringified def _ eq__ (self, another): return hasattr (another, 'Item') and\ hasattr (another) 'Other') and\ self.Item = = another.Item and\ self.Other = = another.Other def _ _ hash__ (self): return hash (self.Item) * 397 ^ hash (self.Other) def _ str__ (self): return self.Stringified# defines the function required to check the spatial connectivity of the area Accurate def buildLookup (items) to ensure the adjacency between the two sides of the region: itemToIndex = {} index = 0 for key in sorted (items): itemToIndex [key] = index index + = 1 return itemToIndex def buildRules (items): itemToIndex = buildLookup (items.keys ()) rulesAdded = {} rules = [] keys = sorted (list (items.keys ()) for key in sorted (items.keys () : keyIndex = itemToIndex [key] adjacentKeys = items [key] for adjacentKey in adjacentKeys: if adjacentKey = ='': continue adjacentIndex = itemToIndex [adjacentKey] temp = keyIndex if adjacentIndex

"+ str (Keys [adjacentIndex]) rule = Rule (temp, adjacentIndex, ruleKey) if rule in rulesAdded: rulesAdded [rule] + = 1 else: rulesAdded [rule] = 1 rules.append (rule) for k V in rulesAdded.items (): if v = = 1: print ("rule% s is not bidirectional"% k) return rules# defines the genomic colors represented by color = ["Orange", "Yellow", "Green", "Blue"] colorLookup = {} for color in colors: colorLookup [color [0]] = colorgeneset = list (colorLookup.keys ()) # define individual genotypes Each individual has 78 genes, each of which represents a region. Individual genes need to satisfy that the adjacent regions in the rules have different colors class GraphColoringTests (unittest.TestCase): def test (self): rules = buildRules (one_neighbor_other) colors = ["Orange", "Yellow", "Green" ColorLookup = {} for color in colors: colorLookup [color [0]] = color geneset = list (colorLookup.keys ()) optimalValue = len (rules) startTime = datetime.datetime.now () fnDisplay = lambda candidate: display (candidate, startTime) fnGetFitness = lambda candidate: getFitness (candidate, rules) best = genetic.getBest (fnGetFitness, fnDisplay, len (one_neighbor_other), optimalValue Geneset) self.assertEqual (best.Fitness, optimalValue) keys = sorted (one_neighbor_other.keys ()) for index in range (len (one_neighbor_other)): print (keys [index], "is", colorLookup [best.Genes]) # output each region color def display (candidate) StartTime): timeDiff = datetime.datetime.now ()-startTime print ("% s\ t% I\ t% s"% ('. Join (map (str, candidate.Genes)), candidate.Fitness, str (timeDiff)) # check whether the color of each region is consistent with the color represented by individual genes def getFitness (candidate) Rules): rulesThatPass = 0 for rule in rules: if candidate [rule.Item]! = candidate [rule.Other]: rulesThatPass + = 1 return rulesThatPass# runtime program GraphColoringTests (). Test () 2.3 result display

   executes the above code to get the result. It is worth mentioning here: this code does not know if it is its own fault, or the problem with my computer, it is very slow to execute-it may take about 5 to 6 hours to run at a time, which is really too slow; if you are interested, you can try to improve the efficiency of the code.

The result after the execution of the    code is in literal form, as shown in the following figure.

   can see that, after 203iterations, found to meet the requirements of the map color scheme, in 06 hours and 06 minutes; the code execution results in addition to showing the overall genotype of a specific individual, will also show 78 small areas (small spots) of their specific color names (I did not truncate the image above, in fact, 78 small areas of the color will be output).

   of course, you can also find that the result of code execution expressed in this kind of text is obviously not as intuitive as a result diagram shown below. However, because the single execution time of the code is too long, I no longer have time (actually lazy) to modify the visualization of the results. If you are interested, you can try to modify the final result rendering part of the code-for example, through the extension of the Matplotlib library-the Basemap library can visualize the color schemes of 78 small areas.

The above is all the contents of this article entitled "how to use genetic algorithm coloring based on the four-color principle of Python map". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.