Symmetry has been a very useful tool to researchers in various scientific fields. At its most basic,symmetry refers to the invariance of an object to some transformation, or set of transformations.Usually one searches for, and uses information concerning an existing symmetry within given data,structure or concept to somehow improve algorithm performance or compress the search space. This thesis examines the effects of imposing or inducing symmetry on a search space. That is, thequestion being asked is whether only existing symmetries can be useful, or whether changingreference to an intuition-based definition of symmetry over the evaluation function can also be ofuse. Within the context of optimization, symmetry induction as defined in this thesis will have theeffect of equating the evaluation of a set of given objects. Group theory is employed to explore possible symmetrical structures inherent in a search space.Additionally, conditions when the search space can have a symmetry induced on it are examined. Theidea of a neighborhood structure then leads to the idea of opposition-based computing which aimsto induce a symmetry of the evaluation function. In this context, the search space can be seen ashaving a symmetry imposed on it. To be useful, it is shown that an opposite map must be definedsuch that it equates elements of the search space which have a relatively large difference in theirrespective evaluations. Using this idea a general framework for employing opposition-based ideasis proposed. To show the efficacy of these ideas, the framework is applied to popular computationalintelligence algorithms within the areas of Monte Carlo optimization, estimation of distribution andneural network learning.The first example application focuses on simulated annealing, a popular Monte Carlo optimizationalgorithm. At a given iteration, symmetry is induced on the system by considering oppositeneighbors. Using this technique, a temporary symmetry over the neighborhood region is induced.This simple algorithm is benchmarked using common real optimization problems and compared againsttraditional simulated annealing as well as a randomized version. The results highlight improvementsin accuracy, reliability and convergence rate. An application to image thresholding furtherconfirms the results. Another example application, population-based incremental learning, is rooted in estimation ofdistribution algorithms. A major problem with these techniques is a rapid loss of diversity withinthe samples after a relatively low number of iterations. The opposite sample is introduced as aremedy to this problem. After proving an increased diversity, a new probability update procedure isdesigned. This opposition-based version of the algorithm is benchmarked using common binaryoptimization problems which have characteristics of deceptivity and attractive basinscharacteristic of difficult real world problems. Experiments reveal improvements in diversity,accuracy, reliability and convergence rate over the traditional approach. Ten instances of thetraveling salesman problem and six image thresholding problems are used to further highlight theimprovements. Finally, gradient-based learning for feedforward neural networks is improved using opposition-basedideas. The opposite transfer function is presented as a simple adaptive neuron which easily allowsfor efficiently jumping in weight space. It is shown that each possible opposite network representsa unique input-output mapping, each having an associated effect on the numerical conditioning ofthe network. Experiments confirm the potential of opposite networks during pre- and early trainingstages. A heuristic for efficiently selecting one opposite network per epoch is presented.Benchmarking focuses on common classification problems and reveals improvements in accuracy,reliability, convergence rate and generalization ability over common backpropagation variants. Tofurther show the potential, the heuristic is applied to resilient propagation where similarimprovements are also found.
PDF
download
878987797
028-85220240
