Evolutionary search algorithms (ESAs from now on) are iterative problem solvers developed with inspiration from neo-Darwinian survival of the fittest genes. This thesis looks at the core issues surrounding ESAs and is a step towards building a rational methodology for their effective use. Currently there is no such method of best practice rather the whole process of designing and using ESAs is seen as more of a black art than a tried and tested engineering tool. Consequently, many non-practitioners are sceptical of the worth of ESAs as a useful tool at all. Therefore the first task of the thesis is to layout the reasons, from computational theory, why ESAs can be a potentially powerful tool. In this context the theory of NP-completeness is introduced to ground the discussions throughout the thesis. Then a simple framework for describing ESAs is developed to form another cornerstone of these later discussions. From here there are two main themes of the thesis. The first theme is that the No Free Lunch result requires us to take a problem centric, as opposed to algorithm centric, perspective on ESA research. The second major theme is the argument that whole algorithms and traditional computer science problem classes are the wrong level of granularity for the focus of our research. Instead we should be researching empirical questions of search bias at the granularity of the components of search algorithms. Furthermore, we should be finding empirical evidence to demonstrate that our granularity of analytic class is such that one analytic class maps onto one search bias class. We will see that this can mean that we have to sub-divide our classic computer science problems classes into smaller sub-classes. The hope is that we can find analytic distinctions that will sub-divide the instances along lines that match the divisions between the various empirically discoverable search bias classes. The intention is to develop our knowledge until we get one analytic class to map into one empirical class. If we have strong empirical evidence to suggest that this has been achieved then we have good grounds on which to confidently use this knowledge to predict the effective search biases required for new problem instances. In the last two chapters of the thesis we demonstrated these ideas on various instances of the euclidean TSP problem class

Entrepreneur plays an important role in the success of start-up companies. According to the past research, the successful rate of entrepreneurial team is much higher than individual. Therefore, ¡§entrepreneurial team¡¨ becomes a significant topic in entrepreneurial research. However, scholars pay more attention on ¡§the complement of competence and resource between members of entrepreneurial team¡¨ rather than ¡§the different schema between entrepreneur and entrepreneurial partner.¡¨ In order to find out the schema difference, this research uses case study of qualitative research method, conducting in-depth interview towards 5 entrepreneurs and 12 entrepreneurial partners. After data coding and persistent thinking, we find 3 main schema differences between entrepreneur and entrepreneurial partner from the perspective of fitness landscape. They are differences in ¡§sight,¡¨ ¡§step¡¨ and ¡§principle.¡¨ For ¡§sight,¡¨ the environment evaluation of entrepreneur is relatively ¡§comprehensive,¡¨ ¡§long-tem¡¨ and ¡§sharp,¡¨ while it of entrepreneurial partner is ¡§partial,¡¨ ¡§short-term¡¨ and ¡§dull.¡¨ For ¡§step,¡¨ entrepreneur¡¦s manner of achieving goal is relatively ¡§risky¡¨ and ¡§hard-working,¡¨ while entrepreneurial partner¡¦s is ¡§conservative¡¨ and ¡§easy.¡¨ For ¡§principle,¡¨ entrepreneur¡¦s rationale of decision making is relatively ¡§finance-oriented,¡¨ while entrepreneurial partner¡¦s is ¡§technology-oriented.¡¨ Besides, the schema differences between entrepreneur and entrepreneurial partner will interact with each other, resulting in further schema change. Besides age and experience, the main factor leads to the schema differences between entrepreneur and entrepreneurial partner is the different ¡§structure¡¨ that entrepreneur and entrepreneurial partner are situated. This research points out the schema differences between entrepreneur and entrepreneurial partner. In practice, this research helps entrepreneur cultivate a better understanding in entrepreneur partner¡¦s schema to facilitate the cooperation and coordination between them. In management education, this research emphasizes the importance of schema cultivation beside technical training.

This study seeks to explain the reasons behind why first-mover advantage is unsustainable in emerging industries. For the purpose of study, four companies in two different industries, namely TFT-LCD backlight module and magnesium alloy enclosure manufactures are categories into two groups based on their entrance position (first-movers and latecomers). Since traditional strategies are much harder to use when analyzing industries undergoing rapid change, thus the concept of fitness landscape is used. The conclusions of this study are presented as follows: 1) Although first-movers advantages exists in mature, stable industry, however, the fast changing nature of emerging industries meant that traditional notions are unfeasible. 2) Four important, inter-related factors determine the possibility of latecomer to overcome first-mover advantages, they are i) the growing market, ii) late entry, iii) revolutionary technology, and iv) focused product strategy. 3) Ever-changing business environment, fitness landscape, meant that static strategies are no longer feasible. The affect of every decision have direct implications for the industry at large, thus changing the landscape. Therefore, constant awareness and mobility are most important to survive in emerging industries.

Os modelos tradicionais de análise de políticas públicas têm sido alvo de críticas devido suas explicações serem marcadas pela dualidade entre agência e estrutura, e também pelo seu caráter linear. Acadêmicos têm chamado atenção para o potencial da teoria da complexidade para área de políticas públicas, entretanto ainda são escassos os estudos neste sentido. Este trabalho contribuiu para a área ao propor um ferramental analítico para a análise de políticas públicas baseado na teoria da complexidade e que pode auxiliar a compreender o processo de formulação de políticas a partir de uma visão holística. Ao aplicar o fitness landscape, à análise do processo de formulação da Política Nacional de Resíduos Sólidos procurou-se compreender como os aspectos estruturais (recursos possuídos pelos atores) e os aspectos de agência (capacidade de articulação na defesa de seus interesses) se relacionam dinamicamente, e em que medida auxiliam na explicação da política que foi formulada. A base de dados foi composta prioritariamente de notas taquigráficas de audiências públicas no período de 10 anos, de 2000 a 2010. Foi construído um código de análise documental buscando identificar os recursos dos atores, e os temas objetos de discussão, e quais atores partilhavam de posições semelhantes. Entrevistas complementares foram realizadas a fim de que se pudesse sanar ambiguidades resultantes da análise documental. Verificou-se que os atores mais influentes (com recursos mais importantes e que conseguiam estabelecer relações com outros atores) conseguiram ter seus objetivos expressos na política e também conseguiam por vezes influir na dinâmica de negociação. A política resultante foi em grande parte reflexo das demandas dos atores com mais alto fitness em cada período. A análise do caso a partir da lente teórica da complexidade, possibilitou resultados diferentes daqueles proporcionados pelas teorias tradicionais, permitindo que a dinâmica pudesse ser incorporada na análise, possibilitando uma explicação holística do processo. / Traditional models of policy analysis have been criticized due to the fact that their explanations have been marked by the duality between agency and structure, and also to its linear character. Scholars have emphasized the potential of complexity theory to the area of public policy, but there are still few studies in this regard. This work contributed to the area by proposing an analytical tool for the analysis of public policies based on complexity theory and that can help in understanding the policy-making process from a holistic view. By applying the fitness landscape to the analysis of the formulation process of the National Solid Waste Policy, I tried to understand how the structural aspects (resources owned by the actors) and aspects of agency (capacity to align to defend their interests) dynamically relate to each other and to what extent, they help explain the policy that was formulated. The database was primarily composed of shorthand notes of public hearings in 10 years, from 2000 to 2010. It was built a code analysis seeking to identify the resources of the actors and the topics of discussion, and which actors shared similar positions. Additional interviews were conducted in order that they could solve ambiguities arising from the documentary analysis. It was found that the most influential actors (with the most important resources and that could establish relations with other actors) got their goals expressed in policy and could also sometimes affect the dynamics of negotiation. The resulting policy was largely a reflection of the demands of the actors with the highest fitness in each period. The case analysis trought the lens of complexity, resulted different outputs from those provided by traditional theories, allowing the time could be incorporated in the analysis, providing a holistic explanation of the process.

Statistical mechanics has been applied to a wide range of systems in physics, biology, medicine and even anthropology. This theory has been recently used to model the complex biochemical processes of gene expression and regulation. In particular, genetic networks offer a large number of interesting phenomena, such as multistability and oscillatory behaviour, that can be modelled with statistical mechanics tools. In the first part of this thesis we introduce gene regulation, genetic switches, and the colonization of a spatially structured media. We also introduce statistical mechanics and some of its useful tools, such as the master equation and mean- field theories. We present simple examples that are both pedagogical and also set the basis for the study of more complicated scenarios. In the second part we consider the exclusive genetic switch, a fundamental example of genetic networks. In this system, two proteins compete to regulate each other's dynamics. We characterize the switch by solving the stationary state in different limits of the protein binding and unbinding rates. We perform a study of the bistability of the system by examining its probability distribution, and by applying information theory techniques. We then present several versions of a mean field theory that offers further information about the switch. Finally, we compute the stationary probability distribution with an exact perturbative approach in the unbinding parameter, obtaining a valid result for a wide range of parameters values. The techniques used for this calculation are successfully applied to other switches. The topic studied in the third part of the thesis is the propagation of a trait inside an expanding population. This trait may represent resistance to an antibiotic or being infected with a certain virus. Although our model accounts for different examples in the genetic context, it is also very useful for the general study of a trait propagating in a population. We compute the speed of expansion and the stationary population densities for the invasion of an established and an expanding population, finding non-trivial criteria for speed selection and interesting speed transitions. The obtained formulae for the different wave speeds show excellent agreement with the results provided by simulations. Moreover, we are able to obtain the value of the speeds through a detailed analysis of the populations, and establish the requirements for our equations to present speed transitions. We finally apply our model to the propagation in a position-dependent fitness landscape. In this situation, the growth rate or the maximum concentration depends on the position. The amplitudes and speeds of the waves are again successfully predicted in every case.

Thesis (MSc)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: Evolutionary Algorithms (EAs) are stochastic techniques, based on the idea of biological evolution, for finding near-optimal solutions to optimisation problems. Due to their generality and computational speed, they have been applied very successfully in a wide range of disciplines. However, as a consequence of their stochasticity and generality, very little has been rigorously established about their performance. Developing models for explaining and predicting algorithmic performance is, in fact, one of the most important challenges facing the field of optimisation. A qualitative version of such a model of EAs is developed in this thesis. There are two paradigms for explaining why EAs are expected to converge toward an optimum. The traditional explanation is that of Universal Darwinism, but an alternative explanation is that they are hill climbing algorithms which utilise all possible escape strategies — restarting local search, stochastic search and acceptance of non-improving solutions. The combination of the hill climbing property and the above escape strategies leads to a fast algorithm that is able to avoid premature convergence. Due to the difficulty in mathematically or empirically explaining the performance of EAs, terms such as exploitation, exploration, intensity and diversity are routinely employed for this purpose. Six prevalent views on exploitation and exploration are identified in the literature, each expressing a different facet of these notions. The coherence of these views is substantiated by their deducibility from the proposed novel definitions of exploitation and exploration. This substantiation is based on a novel hypothetical construct, namely that of a Probable Fitness Landscape (PFL), which both unifies and clarifies the surrounding terminology and our understanding of the performance of EAs. The PFL is developed into a qualitative model of EAs by extending it to the notion of an Ideal Probability Distribution (IPD). This notion, along with the criteria of diversity and computational speed, forms a method for judging the performance of EA operators. It is used to explain why the principal operators of EAs, namely mutation and selection, are effective. There are three main types of EAs, namely Genetic Algorithms (GAs), Evolution Strategies and Evolutionary Programming, each of which employ their own unique operators. Important facets of the crossover operator (which is particular to GAs) are identified, such as: opposite step vectors, genetic drift and ellipsoidal parent-centred probability distributions with variance proportional to the distance between parents. The shape of the crossover probability distribution motivates a comparison with a novel continuous approximation of mutation, which reveals very similar underlying distributions, although for crossover the distribution is adaptive whereas for mutation it is fixed. The PFL and IPD are used to analyse the crossover operator, the results of which are contrasted with the traditional explanations of the Schema Theorem and Building Block Hypothesis as well as the Evolutionary Progress Principle and Genetic Repair Hypothesis. It emerges that the facetwise nature of the PFL extracts more sound conclusions than the other explanations which, falsely, attempt to prove GAs to be superior. / AFRIKAANSE OPSOMMING: Evolusionere Algoritmes (EAs) is stogastiese tegnieke vir die bepaling van naby-optimale oplossings vir optimeringsprobleme wat gebaseer is op die beginsel van biologiese evolusie. As gevolg van hul algemene toepasbaarheid en hoe berekeningspoed, is hierdie algoritmes al met groot sukses in ’n wye verskeidenheid dissiplines toegepas. Die stogastiese aard en algemene toepasbaarheid van hierdie klas van algoritmes het egter tot gevolg dat baie min al oor hul werkverrigting formeel bewys is. Die ontwikkeling van modelle waarmee die doeltreffendheid van algoritmes verklaar en voorspel kan word, is trouens een van die grootste uitdagings in die studieveld van optimering. ’n Kwalitatiewe weergawe van so ’n model word in hierdie verhandeling vir EAs daargestel. Daar bestaan twee paradigmas vir die verklaring van waarom daar van EAs verwag word om na ’n optimum te konvergeer. Die tradisionele verklaring geskied aan die hand van Universele Darwinisme, maar ’n alternatiewe verklaring is dat hierdie algoritmes bergtop-soekend is en van alle moontlike ontsnapstrategiee gebruik maak — lokale soekstrategiee, stogastiese soekstrategiee en die aanvaarding van minderwaardige oplossings. Die kombinasie van die bergtop-soekende eienskap en die insluiting van die bogenoemde ontsnapstrategiee gee aanleiding tot vinnige algoritmes wat daartoe in staat is om voortydige konvergensie te vermy. Omdat dit moeilik is om die werkverrigting van EAs wiskundig of empiries te verklaar, word terminologie soos uitbuiting, verkenning, intensiteit en diversiteit roetinegewys vir hierdie doel ingespan. Ses heersende menings in die literatuur oor uitbuiting en verkenning word ge¨ıdentifiseer wat elkeen ’n ander faset van hierdie begrippe uitlig. Die samehang van hierdie menings word deur hul afleibaarheid uit nuwe definisies van uitbuiting en verkenning gedemonstreer. Hierdie demonstrasie is gebaseer op ’n nuwe hipotetiese konstruk, naamlik die van ’n Waarskynlike Fiksheidslandskap (WFL), wat beide die omliggende terminologie¨e en ons begrip van die werking van EAs enersyds verenig en andersyds verduidelik. Die begrip van ’n WFL word tot ’n kwantitatiewe model vir EAs ontwikkel deur dit tot die konstruk van ’n Ideale Waarskynlikheidsverdeling (IWV) uit te brei. Hierdie konsep word saam met die kriteria van diversiteit en berekeningspoed gebruik om ’n metode te ontwikkel waarmee die werkverrigting van EAs beoordeel kan word. Die IWV word gebruik om te verklaar waarom die hoofoperatore van EAs, naamlik mutasie en seleksie, doeltreffend is. Daar is drie tipes van EAs, naamlik Genetiese Algoritmes (GAs), Evolusionere Strategiee en Evolusionere Programmering, wat elk hul eie, unieke operatore bevat. Belangrike fasette van die oorgangsoperator (wat eie is aan GAs) word uitgelig, soos regoorstaande trapvektore, genetiese neiging en ellipsoıdale ouer-gesentreerde waarskynlikheidsverdelings met variansies wat eweredig is aan die afstand tussen ouers. Die vorm van die oorgangs-waarskynlikheidsverdeling gee aanleiding tot ’n vergelyking tussen die begrip van oorgang en ’n nuwe, kontinue benadering van mutasie. Daar word gevind dat die onderliggende verdelings baie soortgelyk is, alhoewel die oorgangsverdeling aanpasbaar is, terwyl die verdeling vir mutasie vas is. Die WFL en IWV word gebruik om die oorgangsoperator te analiseer en die resultate van hierdie analise word teenoor die tradisionele verklarings van die Skemastelling en Boublok-hipotese sowel as die Evolusionere Vooruitgangsbeginsel en die Genetiese Herstel-hipotese gekontrasteer. Dit blyk dat meer grondige gevolgtrekkings gemaak kan word uit die fasetgewyse aard van die WFL as uit ander verklarings wat valslik poog om die meer doeltreffende werkverrigting van GAs te demonstreer. Die gebruik van faset-gewyse en kwalitatiewe modelle word geregverdig deur hul sukses in terme van die verklaring van EA werkverrigting. Die argument word gemaak dat die beste rigting vir voortgesette navorsing oor EAs is om weg te bly van vergelykende studies en die afleiding van sogenaamde vergelykings van beweging, maar om eerder die ontwikkeling van wetenskaplikgefundeerde, faset-gewyse modelle vir algoritmiese werkverrigting na te streef.

Real-world optimisation problems are often very complex. Population-based metaheuristics, such as evolutionary algorithms and particle swarm optimisation (PSO) algorithms, have been successful in solving many of these problems, but it is well known that they sometimes fail. Over the last few decades the focus of research in the field has been largely on the algorithmic side with relatively little attention being paid to the study of the problems. Questions such as ‘Which algorithm will most accurately solve my problem?’ or ‘Which algorithm will most quickly produce a reasonable answer to my problem?’ remain unanswered. This thesis contributes to the understanding of optimisation problems and what makes them hard for algorithms, in particular PSO algorithms. Fitness landscape analysis techniques are developed to characterise continuous optimisation problems and it is shown that this characterisation can be used to predict PSO failure. An essential feature of this approach is that multiple problem characteristics are analysed together, moving away from the idea of a single measure of problem hardness. The resulting prediction models not only lead to a better understanding of the algorithms themselves, but also takes the field a step closer towards the goal of informed decision-making where the most appropriate algorithm is chosen to solve any new complex problem. / Thesis (PhD)--University of Pretoria, 2014. / Computer Science / unrestricted

The thesis presents a reformative criticism of science funding by peer review. The criticism is based on epistemological scepticism, regarding the ability of scientific peers, or any other agent, to have access to sufficient information regarding the potential of proposed projects at the time of funding. The scepticism is based on the complexity of factors contributing to the merit of scientific projects, and the rate at which the parameters of this complex system change their values. By constructing models of different science funding mechanisms, a construction supported by historical evidence, computational simulations show that in a significant subset of cases it would be better to select research projects by a lottery mechanism than by selection based on peer review. This last result is used to create a template for an alternative funding mechanism that combines the merits of peer review with the benefits of random allocation, while noting that this alternative is not so far removed from current practice as may first appear.

In this paper we present general results on aggregation of variables, specifically as it applies to decomposable (partitionable) dynamical systems. We show that a particular class of transition matrices, namely, those satisfying an equitable partitioning property, are aggregable under appropriate decomposition operators. It is also shown that equitable partitions have a natural application to the description of mutation-selection matrices (fitness landscapes) when their fitness functions have certain symmetries concordant with the neighborhood relationships in the underlying configuration space. We propose that the aggregate variable descriptions of mutation-selection systems offer a potential formal definition of units of selection and evolution.

In this paper, we investigate fitness landscapes (under point mutation and recombination) from the standpoint of whether the induced evolutionary dynamics have a “fast-slow” time scale associated with the differences in relaxation time between local quasi-equilibria and the global equilibrium. This dynamical hevavior has been formally described in the econometrics literature in terms of the spectral properties of the appropriate operator matrices by Simon and Ando (Econometrica 29 (1961) 111), and we use the relations they derive to ask which fitness functions and mutation/recombination operators satisfy these properties. It turns out that quite a wide range of landscapes satisfy the condition (at least trivially) under point mutation given a sufficiently low mutation rate, while the property appears to be difficult to satisfy under genetic recombination. In spite of the fact that Simon-Ando decomposability can be realized over fairly wide range of parameters, it imposes a number of restriction on which landscape partitionings are possible. For these reasons, the Simon-Ando formalism does not appear to be applicable to other forms of decomposition and aggregation of variables that are important in evolutionary systems.