Category: Uncategorized

A new algorithm for solving maximum satisfiability (MAX-SAT) problems is introduced which clusters good solutions, and restarts the search from the closest feasible solution to the centroid of each cluster. This is shown to be highly efficient for finding good solutions of large MAX-SAT problems. We argue that this success is due to the population learning the large-scale structure of the fitness landscape. Systematic studies of the landscape are presented to support this hypothesis. In addition, a number of other strategies are tested to rule out other possible explanations of the success. Preliminary results are shown, indicating that extensions of the proposed algorithm can give similar improvements on other hard optimization problems.

Spin glass optimization is a distributed technique inspired by the interactions in spin glasses in nature. Spin glasses are the lattices of spins where each spin is only a part of the entire solution, in contrast to genetic algorithms (GAs), where each chromosome represents a complete solution. The interaction between spins creates special optimal patterns given appropriate temperature. This optimization paradigm is promising in complex multiobjective optimization tasks because it allows high-computational parallelism among its member spins. Furthermore, since the overall network of spins represents only one solution, there is a great promise in computational efficiency when compared with other population-based/stochastic approaches such as GAs and simulated annealing. The nature of this method is also entirely different from other distributed frameworks such as Hopfield neural network since spins’ paradigm of interaction does not have to be fully connected; i.e., the neighborhoods of interactions can expand or collapse, hence less computation and better convergence speed. In this paper, we apply a heuristic method based on the spin glass model that uses migration and elitism operators in addition to temperature control in order to trace out an efficient frontier in the optimization landscape. The proposed methodology is then applied to the problem of portfolio selection. Portfolio selection is one of the nondeterministic polynomial complete problems where each asset’s behavior is similar to spin’s behavior and it is therefore suitable as a case study. We show that, in proper circumstances, decrementing local energy of each spin can decrement global energy of the glass, and correspondingly, if the optimization problem can be suitably mapped to the glass, the expected cost function decreases.

This paper describes the use of decision maker preferences in terms of the relative importance of objectives in evolutionary multiobjective optimization. A mathematical model of the relative importance of objectives and an elicitation algorithm are proposed, and three methods of incorporating explicated preference information are described and applied to standard test problems in an empirical study. The axiomatic model proposed here formalizes the notion of relative importance of objectives as a partial order that supports strict preference, equality of importance, and incomparability between objective pairs. Unlike most approaches, the proposed model does not encode relative importance as a set of real-valued parameters. Instead, the approach provides a functional correspondence between a coherent overall preference with a subset of the Pareto-optimal front. An elicitation algorithm is also provided to assist a human decision maker in constructing a coherent overall preference. Besides elicitation of a priori preference, an interactive facility is also furnished to enable modification of overall preference while the search progresses. Three techniques of integrating explicated preference information into the well-known Non-dominated Sorting Genetic Algorithm (NSGA)-II are also described and validated in a set of empirical investigation. The approach allows a focus on a subset of the Pareto-front. Validations on test problems demonstrate that the preference-based algorithm gained better convergence as the dimensionality of the problems increased.

To evaluate the search capabilities of a multiobjective algorithm, the usual approach is to choose a benchmark of known problems, to perform a fixed number of function evaluations, and to apply a set of quality indicators. However, while real problems could have hundreds or even thousands of decision variables, current benchmarks are normally adopted with relatively few decision variables (normally from 10 to 30). Furthermore, performing a constant number of evaluations does not provide information about the effort required by an algorithm to get a satisfactory set of solutions; this information would also be of interest in real scenarios, where evaluating the functions defining the problem can be computationally expensive. In this paper, we study the effect of parameter scalability in a number of state-of-the-art multiobjective metaheuristics. We adopt a benchmark of parameter-wise scalable problems (the Zitzler-Deb-Thiele test suite) and analyze the behavior of eight multiobjective metaheuristics on these test problems when using a number of decision variables that range from 8 up to 2048. By using the hypervolume indicator as a stopping condition, we also analyze the computational effort required by each algorithm in order to reach the Pareto front. We conclude that the two analyzed algorithms based on particle swarm optimization and differential evolution yield the best overall results.

We investigate whether XCS, a genetic algorithm based learning classifier system, can harness information from a user’s environment to help desktop applications better personalize themselves to individual users. Specifically, we evaluate XCSs ability to predict user-preferred actions for a calendar and a media player. Results from three real-world user studies indicate that XCS significantly outperforms a decision-tree learner to successfully predict user preferences for these two desktop interfaces. Our results also show that removing external user-related contextual information degrades XCSs performance. This performance degradation emphasizes the need for desktop applications to access external contextual information to better learn user preferences. Our results highlight the potential for a learning classifier systems based approach for personalizing desktop applications to improve the quality of human-computer interaction.

In the above titled paper (ibid., vol. 14, no. 1, pp. 150-169, Feb. 10), some of the results in Tables IV and VI were incorrect. An explanation is presented here.

During the last three decades, several constraint handling techniques have been developed to be used with evolutionary algorithms (EAs). According to the no free lunch theorem, it is impossible for a single constraint handling technique to outperform all other techniques on every problem. In other words, depending on several factors such as the ratio between feasible search space and the whole search space, multimodality of the problem, the chosen EA, and global exploration/local exploitation stages of the search process, different constraint handling methods can be effective during different stages of the search process. Motivated by these observations, we propose an ensemble of constraint handling techniques (ECHT) to solve constrained real-parameter optimization problems, where each constraint handling method has its own population. A distinguishing feature of the ECHT is the usage of every function call by each population associated with each constraint handling technique. Being a general concept, the ECHT can be realized with any existing EA. In this paper, we present two instantiations of the ECHT using four constraint handling methods with the evolutionary programming and differential evolution as the EAs. Experimental results show that the performance of ECHT is better than each single constraint handling method used to form the ensemble with the respective EA, and competitive to the state-of-the-art algorithms.