Asynchronous architecture for evolutionary computation techniques

Abstract

In some embodiments, an archipelago model is provided for distributed execution of evolutionary computing techniques. In some embodiments, an archipelago manager computing device manages a centralized archipelago management queue, and provides population subsets to a plurality of island computing devices. The archipelago manager computing device receives candidate solutions from the island computing devices, stores the candidate solutions in the archipelago management queue, and transmits candidate solutions from the archipelago management queue to the island computing devices in order to exchange candidate solutions between the island computing devices. The use of an archipelago management queue allows transfer of candidate solutions between different island computing devices, is robust to failure of any given island computing device, and does not require homogeneity within the plurality of island computing devices.

1 . A non-transitory computer-readable medium having computer-executable instructions stored thereon that, in response to execution by one or more processors of a computing device, cause the computing device to perform actions for optimizing calculation of an evolutionary computation technique, wherein the evolutionary computation technique includes determining a fitness value for a plurality of individuals in a population, removing a number of individuals from the population based on the fitness values, generating new individuals by combining traits from individuals of the population, and randomly changing traits in one or more individuals in the population, the actions comprising:
 generating an initial population of individuals;   determining capabilities of each island computing device of a plurality of island computing devices, the plurality of island computing devices including a first island computing device;   dividing the initial population into a plurality of population subsets, including sizing each population subset of the plurality of population subsets based on capabilities of a corresponding island computing device; and   transmitting each population subset of the plurality of population subsets to a separate island computing device of the plurality of island computing devices.   
     
     
         2 . The computer-readable medium of  claim 1 , wherein the actions further comprise:
 receiving a first set of candidate solutions from the first island computing device;   storing the first set of candidate solutions in an archipelago management queue;   removing a second set of candidate solutions from the archipelago management queue; and   transmitting the second set of candidate solutions to the first island computing device.   
     
     
         3 . The non-transitory computer-readable medium of  claim 2 , wherein removing the second set of candidate solutions from the archipelago management queue includes:
 determining a number of candidate solutions within the first set of candidate solutions; and   removing a matching number of candidate solutions from the archipelago management queue for inclusion in the second set of candidate solutions.   
     
     
         4 . The non-transitory computer-readable medium of  claim 2 , wherein the actions further comprise:
 receiving a third set of candidate solutions from a third island computing device;   storing the third set of candidate solutions in the archipelago management queue;   removing a fourth set of candidate solutions from the archipelago management queue; and   transmitting the fourth set of candidate solutions to the third island computing device;   wherein the third set of candidate solutions includes a different number of candidate solutions than the first set of candidate solutions.   
     
     
         5 . The non-transitory computer-readable medium of  claim 2 , wherein the actions further comprise:
 receiving a fifth set of candidate solutions from the first island computing device;   storing the fifth set of candidate solutions in the archipelago management queue;   removing a sixth set of candidate solutions from the archipelago management queue; and   transmitting the sixth set of candidate solutions to the first island computing device;   wherein the first set of candidate solutions and the sixth set of candidate solutions include at least one candidate solution generated by a different island computing device.   
     
     
         6 . The non-transitory computer-readable medium of  claim 1 , wherein the actions further comprise:
 receiving top candidate solutions from each island computing device of the plurality of island computing devices;   determining one or more island computing devices to reset based on the top candidate solutions;   generating a new population of individuals;   dividing the new population of individuals into a plurality of new population subsets; and   transmitting each new population subset of the plurality of new population subsets to a separate island computing device of the one or more island computing devices to reset.   
     
     
         7 . The non-transitory computer-readable medium of  claim 6 , wherein generating the new population of individuals includes determining the new population of individuals to avoid overlap with the population subsets previously processed by the one or more island computing devices to reset. 
     
     
         8 . The non-transitory computer-readable medium of  claim 1 , wherein the actions further comprise:
 in response to detecting an end condition, transmitting one or more top candidate solutions to a requesting computing device.   
     
     
         9 . The non-transitory computer-readable medium of  claim 8 , wherein detecting the end condition includes at least one of:
 detecting that a predetermined number of iterations have been executed; and   detecting that a fitness threshold has been reached.   
     
     
         10 . The non-transitory computer-readable medium of  claim 1 , wherein the evolutionary computation technique is configured to find an optimal circuit design, and wherein generating the initial population of individuals includes generating a plurality of proposed circuit designs. 
     
     
         11 - 20 . (canceled) 
     
     
         21 . A computer-implemented method for optimizing calculation of an evolutionary computation technique, wherein the evolutionary computation technique includes determining a fitness value for a plurality of individuals in a population, removing a number of individuals from the population based on the fitness values, generating new individuals by combining traits from individuals of the population, and randomly changing traits in one or more individuals in the population, the method comprising:
 generating an initial population of individuals;   determining capabilities of each island computing device of a plurality of island computing devices, the plurality of island computing devices including a first island computing device;   dividing the initial population into a plurality of population subsets, including sizing each population subset of the plurality of population subsets based on capabilities of a corresponding island computing device; and   transmitting each population subset of the plurality of population subsets to a separate island computing device of the plurality of island computing devices.   
     
     
         22 . The method of  claim 21 , further comprising:
 receiving a first set of candidate solutions from the first island computing device;   storing the first set of candidate solutions in an archipelago management queue;   removing a second set of candidate solutions from the archipelago management queue; and   transmitting the second set of candidate solutions to the first island computing device.   
     
     
         23 . The method of  claim 22 , wherein removing the second set of candidate solutions from the archipelago management queue includes:
 determining a number of candidate solutions within the first set of candidate solutions; and   removing a matching number of candidate solutions from the archipelago management queue for inclusion in the second set of candidate solutions.   
     
     
         24 . The method of  claim 22 , further comprising:
 receiving a third set of candidate solutions from a third island computing device;   storing the third set of candidate solutions in the archipelago management queue;   removing a fourth set of candidate solutions from the archipelago management queue; and   transmitting the fourth set of candidate solutions to the third island computing device;   wherein the third set of candidate solutions includes a different number of candidate solutions than the first set of candidate solutions.   
     
     
         25 . The method of  claim 22 , further comprising:
 receiving a fifth set of candidate solutions from the first island computing device;   storing the fifth set of candidate solutions in the archipelago management queue;   removing a sixth set of candidate solutions from the archipelago management queue; and   transmitting the sixth set of candidate solutions to the first island computing device;   wherein the first set of candidate solutions and the sixth set of candidate solutions include at least one candidate solution generated by a different island computing device.   
     
     
         26 . The method of  claim 21 , further comprising:
 receiving top candidate solutions from each island computing device of the plurality of island computing devices;   determining one or more island computing devices to reset based on the top candidate solutions;   generating a new population of individuals;   dividing the new population of individuals into a plurality of new population subsets; and   transmitting each new population subset of the plurality of new population subsets to a separate island computing device of the one or more island computing devices to reset.   
     
     
         27 . The method of  claim 26 , wherein generating the new population of individuals includes determining the new population of individuals to avoid overlap with the population subsets previously processed by the one or more island computing devices to reset. 
     
     
         28 . The method of  claim 21 , further comprising:
 in response to detecting an end condition, transmitting one or more top candidate solutions to a requesting computing device.   
     
     
         29 . The method of  claim 28 , wherein detecting the end condition includes at least one of:
 detecting that a predetermined number of iterations have been executed; and   detecting that a fitness threshold has been reached.   
     
     
         30 . The method of  claim 21 , wherein the evolutionary computation technique is configured to find an optimal circuit design, and wherein generating the initial population of individuals includes generating a plurality of proposed circuit designs.