Evolutionary algorithms (EAs) are a class of population-based stochastic search algorithms which have proven themselves to be powerful tools in optimization problems where the search space is complex, contains many local optima, and is so large that an exhaustive search is not possible. An application area where EAs have great potential is in the design of electronic circuits. However, for this type of task such a large representation is typically required for each of the proposed solutions that using an EA approach is not feasible because of the immense computational power this would require. This limitation of EAs is known as the scalability problem: EAs perform well when dealing with problems requiring a small solution representation, but when the required size for these representations increases the EAs quickly become too computationally expensive to be useful. Numerous approaches for dealing with the scalability problem have been proposed. One of the more promising approaches is inspired by the way nature copes with scaling: the process of an organism growing from a single fertilized cell and into a multi-cellular being, called development. By adapting some of the mechanisms of development to a computer program, the EA can evolve a relatively small genome which when developed i.e. decompressed, using this program will represent a solution. There are, however, some problems regarding this approach. One issue is that biological development is such a complex process that implementing it in all its detail is neither feasible nor desired, meaning a decision regarding which mechanisms to implement and which ones to leave out must be made. Another issue is the increased difficulty to evolve a good solution. This occurs because EAs depend on a gradual refinement of the solution to be effective, but with this approach a small change in the genome may lead to a large change in the corresponding solution. This is because in this approach there is no longer a direct correspondence between the genotype space and the solution space, so that what is adjacent in the genotype space may be far apart in the solution space. This means that even though gradual refinement is achieved in genotype space, the changes in the corresponding solution space may appear to be more or less random A novel artificial development system, designed and implemented from scratch, is presented in this thesis. A novel system was built because, although a number of other such system already have been implemented, they are all in the experimental stage, and this system is though to be a useful supplement to the existing ones, providing more material to base the understanding of what may be useful in an artificial development system on. An explorative approach was taken where the implemented system was put through a number of tests to investigate its capabilities. First the systems ability to develop a varied set of different shapes was investigated. Secondly, four parameters were tested for their effect on the system's ability to develop good solutions: the initial number of neighbours, the number of chemical types used (both part of a precondition), the number of cell types available to the system, and the degree of symmetry in the target shapes. The experiments performed showed that the system is able to develop a number of shapes. For the four investigated parameters, indications were found that each has a profound effect on the systems ability to develop a given target.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:ntnu-10769 |
| Date | January 2006 |
| Creators | Høye, Johan |
| Publisher | Norges teknisk-naturvitenskapelige universitet, Institutt for datateknikk og informasjonsvitenskap, Institutt for datateknikk og informasjonsvitenskap |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0021 seconds