Distributed genetic algorithm research

zhaozj2021-02-16 111

Chapter 5 Research on Distributed Genetic Algorithm

5.1 Profile of distributed genetic algorithm

The basic structure and characteristics of the genetic algorithm determine it is particularly suitable for large-scale parallel. Some studies have shown that evolution calculations on parallel or distributed systems can not only improve the quality of the speed and solution of the solution, but can even obtain superlinear acceleration ratio. Therefore, in recent years, research on parallel implementation of genetic algorithms has been widely valued.

The distributed genetic algorithm generally implements the coarse particle size and group-level parallel, the interaction between the sub-groups is weak, mainly relying on some almost series of genetic algorithms to speed up the search process. The parallelism of the group is to divide a large group into some subgroups according to the structure of the hardware, which is generally evolved independently, ie they choose and gene in the inside, but they are only exchanged between subgroups through certain algex. Some information, the so-called migration model.

In the migration model, the organizational mode of the group is usually a large group divided into some subgroups, each subgroup self-a unit, just implementing an individual's migration between the subgroup, i.e., the individual migrated from one sub-group to another The population, how much migration is usually determined by two parameters: migration frequency and mobility. The size of these two parameters and the way to migrate determine the difference between the migration model. If the individual's migration is completely random, it is randomly sampled from the subgroup, and then randomly migrates to another group, then these sub-groups can be considered completely independent, individual selection and migration. The subgroups are all right, that is, it is equivalent to seeing these subgroups as some independent islands, and individuals from one island to another island will be equal, this migration mode is called "island" model, it is research More models. When implementing parallel, the interconnection of the subgroup can either a total line shape or an annular, or a two-dimensional array, a super cube, or the like. The neighboring relationship between the sub-groups can be determined according to the interconnection mode, thereby migrating the individual to the adjacent subpower having a large probability, thus being migrated, referred to as the "foot step" model.

5.2 Implementation and algorithm of distributed genetic algorithm

With the gradual application of high-performance microcomputer represented by high frequency Pentium II, Pentium II, AMD K-7, the performance of the microcomputer has been greatly improved, and the calculation speed has been comparable to the previous small machine, medium machine, The improvement of network speed and price reduction also makes 10m, 100m or even Gigabit Ethernet. The hardware conditions for distributed computing are easier to satisfy. On the other hand, high-performance parallel computer prices are high, most people are not familiar with their hardware and software. Therefore, the author's research focuses on the research on the distributed genetic algorithm in the microcomputer environment.

From the microcomputer operating system, the most popular is Microsoft's Windows operating system (including Windows 9x series and NT series, as well as the latest 2000 series), and Linux operating system, due to the authors can get research environment for high performance Windows Workstation, so the implementation of distributed genetic algorithm in the Windows environment.

How to make a distributed operation in a Windows environment, there are more methods, the following is the most commonly used:

(1) Use Microsoft's DCOM standard;

(2) Adopt distributed object CORBA standards;

(3) Programming by Windows Socket;

DCOM technology is recommended by Microsoft, more mature, more development tools. CORBA technology can communicate across platforms, which can communicate under Windows and UNIX systems, but there are fewer development tools, generally developed by Borland's Builder Series. At present, the technical data of DCOM and CORBA is small, and the bottom level of DCOM and CORBA is actually implemented by TCP / IP protocol. Windows socket is a programming interface for TCP / IP protocols in a Windows environment, which can think of Windows Socket technology is higher than DCOM. And CORBA technology is more underdeveloped, while DCOM and CORBA have many object-oriented implementations, which can implement transparent access to objects in a network environment. In these three technologies, the author is most familiar to programming Windows Socket. Since the focus of this study is not to establish a very perfect distributed environment, this chapter uses Windows Socket programming. The transport protocol in the TCP / IP protocol has a connected TCP protocol and a connected UDP protocol. Since the author's experimental environment is 100m high-speed local area network, and the amount of transmitted data is not too large, so it has chosen the efficiency slightly lower. However, the programming relatively simple TCP protocol acts as a transmission protocol.

Distributed implementation adopts customer server mode, that is, data transmission is only between customers and servers, and there is no direct communication between customers, and customer data is handled by the server. The server is relatively simple, the main function is to buffer data from each customer, waiting for the synchronization between the customers, and exchange data corresponding to each customer according to certain policy exchanges and send back the exchanged data back to the customer. Based on the communication of customer server needs to follow certain protocols, the authors use the following ideas to establish the corresponding communication protocol, named DISTRIBUTED Genetic Algorithmic Protocol.

During the calculation of distributed genetic plans, each sub-group is not allowed to exit in the middle. Since the amount of genetic planned itself is large, it is generally said that a customer corresponds to a computer, so there is a different customer server program. In the beginning phase, you must clearly know the number of customers (computing workstations) participating in the calculation, and the server is connected to the client and verified, and the client will start the calculated command, each client starts calculation. When the client evolves into the specified algebra, the pauses, each customer communicates separately with the server, upload individual gene data for exchange, and then wait for the server to contact yourself again, get the server after processed gene data, will These gene data are converted to the corresponding individual to join the current group and continue the iterative process. Repeat the above procedure until the ends of each client can be completed, and the output is output.

During the above process, if any network error occurs, the entire distributed calculation is failed. The above model is based on the traditional distributed calculation. It is feasible when the network environment is good. Since the background of the experiment is a high-speed local area network, the condition can be realized. If the network condition is not good, for example, when implementing on a wide area, the model is not suitable, and appropriate modifications must be made.

Below is the runtime process of customers and servers:

For customers:

(1) Connect the server;

(2) Enter the basic parameters and get verified;

(3) Start calculation;

(4) to the set algebra, send the gene data of the exchange individual to the server, and wait for the server to send back the data;

(5) Get the data sent back by the server, convert the data into a corresponding individual, randomly replace the individual of the current group, continue the operation; for the server:

(1) Waiting for the customer's connection request;

(2) Accept the customer;

(3) Verify the customer parameters, the verification failed, sent an error code to the customer, and continues;

(4) Waiting for the customer to upload genetic data, if only some of the customer's data is obtained, the customer waiting for the data;

(5) Get all customers' data, switch gene data, and back the data;

The most powerful tool for the communication protocol is to indicate a limited state machine, Figure 5.1 is a limited state machine that interacts with the customer side, which is worth emphasizing that a limited state machine is different for different customers.

Unchecked

State

Para

State

Checked

State

Data

State

Ready

State

Figure 5.1

The conditions for the metastasis of the finite state machine are as follows:

(1) If the current status is unchecked_state, transfer to the status of the command string "PARA" to the status para_state;

(2) If the current state is para_state, when the customer sent the correct data string "ID gnenumber Exchangemember Exchangefrequency" (the data string is the meaning of the problem, this data is the same as the same problem, the second A parameter means that the number of individuals exchanged, the third parameter means that the number of genes per individual, the fourth parameter intended to switch to the state check_state, if this is the first customer, communication, The parameter is intended as a parameter for distributed calculations. If it is not the first customer, its parameters are required to match the existing parameters. Otherwise, the server sends an error code to the customer, and does not do status transfer;

(3) If the current state is Checked_State, go to the status data_state when the customer is sent to the command string "DATA";

(4) If the current state is DATA_STATE, accept the genetic data sent by the customer, if the data is all, that is, each customer has sent the data, then exchange data according to certain policy, and transfer the data back to the customer, status transfer To checkage_state, if the data is not full, enter ready_stat

E, the remote customer is waiting for the data phase;

Note that the conversion between the state machines here is in the server, that is, the socket (socket) that is actually interacting with the client.

There are two situations where the distributed genetic algorithm program customers have:

(1) Abnormal exit (the client calculation has problems, when the customer sends a command "Abort

", The reason for this happens is that the client has an error or in the debug phase, it needs to be interrupted in advance;

(2) Normal exit (the customer calculation ends, when the customer sends "Success" to the server;

With a typical client server, the various sockets of the server are in the same thread. Therefore, effective communication form is to process the information incorporated as possible. Generally speaking, the data of the mutual transmission should not be too large. The advantage of single thread is that there is no need to consider synchronization issues. Of course, it will be more flexible, but the programming is more complicated, and the synchronization between the thread is needed. Since the research focuses on this chapter is that the distributed genetic algorithm itself, there is no in-depth study in multi-threaded aspects. The server of this distributed calculation uses a single-threaded manner. In the implementation of the distributed genetic algorithm of this chapter, the way to exchange individuals is commonly used roulette, so the more appropriate, the more expensive individuals, the more suitable for the exchange, the more easily selected for exchange.

The process of processing the individual client gene information in the server side uses sequential exchange. First, multiple customers are first random, and then the individual's gene information is sequentially exchanged. Take three customers as an example, suppose

The current random order is the customer 1, customer 2, customer 3, then first telew the individual data of the client 3, and will replace the client 3 with the data of the client 2, the customer 1 data replacement customers 2, and finally the data will be temporarily stored Alternative customers 1 data. That is, as shown below:

Customer 1

Customer 2

Customer 3

Figure 5.2

Obviously this algorithm is "island" model.

§5.3 Case

First, the case is the most designed one of the ten poles, see Chapter 3, and sets it once every 50 generation. The replication probability of the genetic algorithm is 0.2, the mutation probability is 0.01, the mass size is 100, the gene is 100, and does not perform intraction. After retaining the optimal individual in each generation, exchange, so the optimal individual may not be retained. The number of individuals performed in exchange is 10.

With two customers, distributed on two machines, randomly run ten times to get Table 5.1 Results:

(The unit in the form is

)

Customer (1)

Customer (2)

Customer is best to solve

Do not add the single customer, run ten times random

1772.094299

1764.151498

1772.094299

1794.260703

1779.837576

1769.668159

2090.602323

1621.497349

1981.622290

1948.023518

1949.427623

1948.023518

1914.366377

1860.511557

1851.945769

1870.663998

1649.238782

1655.195882

1649.238782

1952.102121

1858.924903

1819.534603

1747.285256

1741.668833

1969.807850

1678.143404

1836.965464

1956.165842

1913.278532

1927.660266

Average 1787.2

Average 1780.4

Mean 1915.7586

Optimum 1621.497349

Optimality 1794.260703

Table 5.1

Table 5.1 The optimal solution in the customer (1), customer (2) is the best solution. It can clearly see the effects of the exchange, whether it is a mean or the optimal solution, has a significant improvement. Another obvious result is that the optimal solution of each customer is small, which is also the direct consequences of mutual delivery of gene data between each customer. Table 5.1 The calculation result of the single customer who is not taken in Table 5.1 is selected from the third chapter of the paper.

If the optimal individual of the current customer group is retained after exchange, it will learn from the concept of single customer genetic steady state algorithm. The genetic parameters are unchanged, the transmission method between the individual is unchanged, randomly runs ten times, the calculation results are shown in the table 5.2: Customers (1)

Customer (2)

Customer is best to solve

Do not add the single customer, run ten times random

1791.311337

1834.738848

1791.311337

1794.260703

1788.344995

1779.779207

2090.602323

1828.117367

1818.288628

1981.622290

1652.387671

1914.366377

1882.371234

1880.385534

1870.663998

1768.064530

1799.295530

1768.064530

1952.102121

1737.074445

1741.286762

1737.074445

1819.534603

1735.969625

1730.253441

1969.807850

1835.736465

1850.840948

1835.736465

1836.965464

1731.217107

1743.754295

1731.217107

1927.660266

Mean 1775.05948

Average 1783.10109

Mean value 1772.44984

Mean 1915.7586

Optimum 1652.387671

Optimality 1794.260703

Table 5.2

The result of the calculation is similar to that of not retained. It can be seen that since each sub-individual is exchanged with a larger probability to select an individual, such a population can ensure that the entire distributed calculation reflects "steady state" to some extent. The following is considered to reserve the optimal individual before exchange and exchange, which can be desired to obtain similar results.

Keeping the genetic parameters unchanged, the transmission method between the individual is unchanged, before exchange and exchange before exchange, and then run ten times, the calculation results are shown in Table 5.3:

Customer (1)

Customer (2)

Customer is best to solve

Do not add the single customer, run ten times random

1878.823298

1876.015087

1794.260703

1964.614892

1962.047598

2090.602323

1729.613478

1981.622290

1675.393562

1914.366377

1750.774823

1870.663998

1732.521451

1728.550050

1952.102121

1871.520460

1819.534603

1885.079683

1969.807850

1636.701594

1836.965464

1656.018393

1927.660266

Average 1778.10616

Average 1777.17147

Mean 1915.7586

Optimum 1636.701594

Optimality 1794.260703 Table 5.3

If a single target genetic plan adopts the intanation algorithm proposed in Chapter 3 of the Papers, the genetic parameters are unchanged, the transmission mode between the individual is unchanged, randomly runs ten times, the calculation results are shown in Table 5.4:

Customer (1)

Customer (2)

Customer is best to solve

Prach customers, randomly run ten times

1598.931898

1724.977697

1656.259310

1661.152983

1656.259310

1665.747371

1752.378452

1768.986802

1752.378452

1665.024621

1753.200963

1760.338228

1761.384680

1756.931447

1612.150443

1847.052096

1798.614174

1598.931898

1746.421352

1625.128071

1744.676568

1632.929717

1849.743569

1833.268932

1668.414427

Average 1705.9466

Mean value 1707.65148

Average 1705.50128

Average 1723.61085

Optimum 1598.931898

Optimum 1612.150443

Table 5.4

The effect of solving is quite satisfactory, and it has been obtained twice, respectively, according to the continuous optimal solution estimation. The outstanding single customer, randomly runs ten times to select the third chapter of the paper.

The above example illustrates that the distributed genetic algorithm is successful.

The effects of different CSF and different migration individuals will be discussed, and the generation is 25, the number of migrated individuals is 5, the other parameters are unchanged, and do not take the test, randomly run ten times, the calculation results are shown in Table 5.5 :

Customer (1)

Customer (2)

Customer is best to solve

Do not add the single customer, run ten times random

1622.801693

1794.260703

1845.008027

2090.602323

1752.178929

1750.774823

1981.622290

1670.499889

1914.366377

1693.688327

1671.663078

1870.663998

1948.388613

1922.450332

1952.102121

1677.379262

1819.534603

1680.287235

1969.807850

1845.730776

1836.965464

1640.913910

1927.660266

Average 1737.68767

Average 1732.7509

Mean 1915.7586

Optimum 1622.801693

Optimality 1794.260703 Table 5.5

After the above table, it can be seen that after reducing the individual, the computational performance has decreased.

Adding a distributed computer to 3, the generation is 50, the number of migrated individuals is 10, randomly runs ten times, does not use the test, the calculation results are shown in Table 5.6:

Customer (1)

Customer (2)

Customer (3)

Customer is best to solve

Do not add the single customer, run ten times random

1628.758793

1794.260703

1625.128071

1689.617165

1625.128071

2090.602323

1610.264504

1981.622290

1636.360915

1635.779321

1636.360915

1635.779321

1914.366377

1746.379959

1724.678412

1726.082517

1724.678412

1870.663998

1611.327932

1646.671487

1611.327932

1952.102121

1688.271429

1680.910223

1688.271429

1680.910223

1819.534603

1692.525138

1700.368177

1690.398283

1969.807850

1614.958654

1615.781165

1614.958654

1836.965464

1632.148599

1927.660266

Mean value 1648.6124

Mean value 1649.96662

Mean value 1652.90113

Mean value 1645.43528

Mean 1915.7586

Optimum 1610.264504

Optimality 1794.260703

Table 5.6

The overall performance of solving is further improved.

In the above example, the number of populations used is 100, which is now reduced to 50, and the other parameters are unchanged. It does not use takeout, randomly running ten times, and the calculation results are shown in Table 5.7:

Customer (1)

Customer (2)

Customer (3)

Customer is best to solve

Do not add the single customer, run ten times random

1614.717737

1794.260703

1636.360915

1634.375215

2090.602323

1730.535750

1981.622290

1847.392774

1914.366377

1737.855563

1870.663998

1623.964882

1952.102121

1806.033749

1819.534603

1667.309607

1667.3096071667.309607

1969.807850

1776.182436

1836.965464

1717.176051

1927.660266

Average 1715.75295

Average 1715.55438

Mean 1915.7586

Optimum 1614.717737

Optimality 1794.260703

Table 5.7

It can be seen from the above table that after the distribution is made, the size of the population can be reduced under the premise of maintaining calculation performance.

Reference [37] pointed out that if the individual does not migrate, the optimal solution among the various customers is generally better than the optimal solution of each customer after migration, but the average performance of the distributed genetic algorithm for migration It is stronger than the average performance of various customers who do not migrate. The genetic algorithm based on this document is a traditional genetic algorithm.

The author of this article also discovered the above phenomenon in the calculation, and also found that the optimization of the distributed genetic algorithm for migration, the genetic algorithm of the dispersion of the solution is not the migration of the genetic algorithm for migration is reduced, and the specific performance is the optimal solution and mean no big difference. Therefore, it is effective to use a distributed genetic algorithm.

Calculate two commonly used optimization examples below:

Twenty-five poles the light weight design, the structure topology is shown in Figure 5.3, each rod material data is the same,

The lower limit of the element size is

, Constraints are displacement and stress constraints, and the displacement constraint is each node.

﹑

To maximum allowable displacement

The variable number is reduced to 8 groups by variable link method, and the stress values allowed by each group are as follows:

Variable group

Stress

Compressive stress

40000

-35092

2-5

40000

-11590

6-9

40000

-17305

10,11

40000

-35092

12,13

40000

-35092

14-17

40000

-6759

18-21

40000

-6759

22-25

40000

-11082

Table 5.8

The working conditions are as follows:

Working condition

Toad node

1000

10,000

-5000

10,000

-5000

500

20000

-5000

-20000

-5000

Table 5.9

Figure 5.3

Group variables of each customer have been indicated by 10 binary, and the lower limit is 0.01

The upper limit is 10.0

The customer's group is taken 50, the genetic algebra is 500, and the interchange of individual gene data is performed every 50 generations.

The genetic parameters of each subgroup are the same, the replication probability is 0.2, and the probability of the variation is 0.01. The results obtained by using three customers randomly run ten times (units are

Customer (1)

Customer (2)

Customer (3)

Customer is best to solve

571.245043

553.787599

557.366130

553.335176

549.329981

554.391384

554.079417554.079417

550.694287

550.798439

551.319769

550.694287

567.190836

559.226085

553.134723

Mean 556.97012

Mean 556.98054

Mean 557.00148

Mean 556.93893

Optimum 549.329981

Table 5.10

The resulting decision scale method in the planning method can be obtained for this problem.

The rod area is distributed below:

Rod set

Initial value

Optimal solution

6.0

0.010000

6.0

1.874632

6.0

3.074175

6.0

0.010000

6.0

0.010000

6.0

0.697805

Seduce

6.0

1.744224

6.0

2.606997

Table 5.11

It can be seen that the results of using distributed genetic algorithms are quite satisfactory. Moreover, the results of each customer are very small.

72 rod structure Lighter weight design, structural topology is shown in Figure 5.4,

The lower limit of the element size is

. The tensile stress limit is

. Displacement constraints for all non-constrained nodes

﹑

The direction of the direction is smaller than

The variable is linked:

1-4

5-12

13-16

17-18

19-22

23-30

Seduce

31-34

35-36

37-40

41-48

49-52

53-54

55-58

59-66

67-70

71-72

Table 5.11

The working conditions are as follows:

Working condition

Load node

5000

-5000

Table 5.12

Figure 5.4

Group variables of each customer have been expressed in 10 binary, and the lower limit is 0.1

The upper limit is 10.0

Since the problem has more variables, the size of the group needs to be obtained accordingly. The calculation is 100, the genetic algebra is 500, and the interchange of individual gene data is performed every 50 generation, the genetic parameters of each sub-group are the same, The probability of replication is 0.2, and the mutation probability is 0.01. The results obtained by using three customers randomly run ten times (units are

Customer (1)

Customer (2)

Customer (3)

Customer is best to solve

391.620056

392.930853

395.879890

391.620056

408.732546

407.156988

417.091071

407.156988

402.305167

393.633959

389.778723

397.268130

399.885940

398.837360

397.268130

398.660375

397.240431

394.086546

395.851459

397.682618

394.086546

423.421803

413.607778

400.270988

392.477760

403.180176

392.477760

421.313826

421.778342421.698643

421.313826

391.300180

393.477327

394.422355

391.300180

400.223504

403.183229

402.144539

400.223504

395.417922

406.276166

395.417922

Mean 402.05175

Mean 400.5535

Mean 403.15331

Mean 399.29099

Optimality 391.300180

Optimality 392.930853

Optimality 389.778723

Table 5.13

The resulting decision scale method in the planning method can be obtained for this problem.

The rod area is distributed below:

Rod set

Initial value

Optimal solution

6.0

0.156615

6.0

0.545346

6.0

0.413460

6.0

0.565005

6.0

0.513471

6.0

0.516821

Seduce

6.0

0.100000

6.0

0.100000

6.0

1.268083

6.0

0.512752

6.0

0.100000

6.0

0.100000

6.0

1.892414

6.0

0.512741

6.0

0.100000

6.0

0.100000

Table 5.14

The calculation results are satisfactory.

As can be seen from the above example, the distributed genetic algorithm proposed by the author is effective, the calculation results are satisfactory, the author believes that the use of binary encoded distributed genetic algorithms is a good solution to small and medium-sized optimization problems. Method, if the problem is not large, consider using the test strategy proposed in the customer genetic planning program.

§5.4 Conclusions and Further Work

This chapter proposes an implementation of distributed genetic algorithm in the local area network microcomputer environment, and establishing a communication protocol for distributed genetic algorithms - "DGAP", individual migration and use is "island" model, customer group An individual who chooses to migrate is used to "roulette" in accordance with the adaptation. Multiple examples indicate that the algorithm calculates performance satisfactory. A "steady state" is jointly maintained between the groups, while the size of each population can be reduced accordingly.

Due to the time relationship, it is also due to more content of the distributed genetic algorithm, the author believes that there is more work in distributed genetic algorithms.

One of the focus is to study the new exchange of exchanges, such as the assessment of the sub-group, that is, the ranking, will be different depending on the ranking when switching. For example, the first group is exchanged with the second group, and the second group exchanges individuals with the third group. The advantage of doing this is to prevent exchange of individuals between groups (ie, the worst group is exchanged between the optimal group), resulting in a decrease in the optimal performance of the distributed genetic algorithm. Alternatively, different genetic parameters (copy probability, variation probability, etc.) can be considering different customers, so that customers' diversity can be added to some extent.

For problems, the model analysis itself, it takes a time-effective problem that the group can be distributed to the network environment. Of course, this is different from the general distributed genetic algorithm in nature. It is actually just a group here. It can be considered a distributed calculation of a single population.

Finally, the author believes that establishing a distributed computing programming environment that is completely complete and autonomous copyright is necessary. The best way is based on UDP-based socket programming, such efficiency, cross-platform, etc. have sufficient guarantees, and the disadvantage is that the programming is more difficult. Of course, mature distributed computing standards DCOM and CORBA can be used.

转载请注明原文地址:https://www.9cbs.com/read-15204.html

9cbs

New Post(0)