Imperialist competitive algorithm combined with chaos for global optimization

A novel chaotic improved imperialist competitive algorithm (CICA) is presented for global optimization. The ICA is a new meta-heuristic optimization developed based on a socio-politically motivated strategy and contains two main steps: the movement of the colonies and the imperialistic competition. Here different chaotic maps are utilized to improve the movement step of the algorithm. Seven different chaotic maps are investigated and the Logistic and Sinusoidal maps are found as the best choices. Comparing the new algorithm with the other ICA-based methods demonstrates the superiority of the CICA for the benchmark functions.     

Permutation-induced acyclic networks for the job shop scheduling problem

In the literature of the combinatorial optimization problems, it is a commonplace to find more than one mathematical model for the same problem. The significance of a model may be measured in terms of the efficiency of the solution algorithms that can be built upon it. The purpose of this article is to present a new network model for the well known combinatorial optimization problem – the job shop scheduling problem. The new network model has similar structure as the disjunctive graph model except that it uses permutations of jobs as decision variables instead of the binary decision variables associated with the disjunctive arcs. To assess the significance of the new model, the performances of exact branch-and-bound algorithmic implementations that are based on both the new model and the disjunctive graph model are compared.     

Optimal server resource reservation policies for priority classes of users under cyclic non-homogeneous markov modeling

Resource availability optimization is studied on a server–client system where different users are partitioned into priority classes. The aim is to provide higher resource availability according to the priority of each class. For this purpose, resource reservation is modeled by a homogeneous continuous time Markov chain (CTMC), but also by a cyclic non-homogeneous Markov chain (CNHMC) as there is a cyclic behavior of the users’ requests for resources. The contribution of the work presented consists in the formulation of a multiobjective optimization problem for both the above cases that aims to determine the optimal resource reservation policy providing higher levels of resource availability for all classes. The optimization problem is solved either with known methods or with a proposed kind of heuristic algorithm. Finally, explicit generalized approximate inverse preconditioning methods are adopted for solving efficiently sparse linear systems that are derived, in order to compute resource availability.     

First passage time for multivariate jump‐diffusion processes in finance and other areas of applications

The first passage time (FPT) problem is an important problem with a wide range of applications in science, engineering, economics, and industry. Mathematically, such a problem can be reduced to estimating the probability of a stochastic process first to reach a boundary level. In most important applications in the financial industry, the FPT problem does not have an analytical solution and the development of efficient numerical methods becomes the only practical avenue for its solution. Most of our examples in this contribution are centered around the evaluation of default correlations in credit risk analysis, where we are concerned with the joint defaults of several correlated firms, the task that is reducible to a FPT problem. This task represents a great challenge for jump‐diffusion processes (JDP). In this contribution, we develop further our previous fast Monte Carlo method in the case of multivariate (and correlated) JDP. This generalization allows us, among other things, to evaluate the default events of several correlated assets based on a set of empirical data. The developed technique is an efficient tool for a number of financial, economic, and business applications, such as credit analysis, barrier option pricing, macroeconomic dynamics, and the evaluation of risk, as well as for a number of other areas of applications in science and engineering, where the FPT problem arises. Copyright © 2008 John Wiley & Sons, Ltd.     

On the analysis of a dynamic evolutionary algorithm

Evolutionary algorithms are applied as problem-independent optimization algorithms. They are quite efficient in many situations. However, it is difficult to analyze even the behavior of simple variants of evolutionary algorithms like the (1+1) EA on rather simple functions. Nevertheless, only the analysis of the expected run time and the success probability within a given number of steps can guide the choice of the free parameters of the algorithms. Here static (1+1) EAs with a fixed mutation probability are compared with dynamic (1+1) EAs with a simple schedule for the variation of the mutation probability. The dynamic variant is first analyzed for functions typically chosen as example-functions for evolutionary algorithms. Afterwards, it is shown that it can be essential to choose the suitable variant of the (1+1) EA. More precisely, functions are presented where each static (1+1) EA has exponential expected run time while the dynamic variant has polynomial expected run time. For other functions it is shown that the dynamic (1+1) EA has exponential expected run time while a static (1+1) EA with a good choice of the mutation probability has polynomial run time with overwhelming probability.     

Evolutionary dynamics of knowledge

This study discusses the evolutionary nature of knowledge acquisition at micro and macro levels, and in particular when the process involves an artificial agent's interpretative devices. In order to accomplish this, we propose using an individual learning model (or inner‐world reconstruction model) that in our view overcomes neoclassic epistemological holdups and may increase the predictive power of computational economics, by letting an artificial agent's knowledge evolve by itself, irrespective of globally specified goals or individual motives of behavior; using simultaneous (or parallel) genetic algorithms (GA) to evolve a single agent's learning strategy, each GA with different general specifications, in a multiagent setting. © 2006 Wiley Periodicals, Inc. Complexity 11: 12–19, 2006     

An approximation algorithm for a facility location problem with stochastic demands and inventories

We propose a 2-approximation algorithm for a facility location problem with stochastic demands. At open facilities, inventory is kept such that arriving requests find a zero inventory with (at most) some pre-specified probability. Costs incurred are expected transportation costs, facility operating costs and inventory costs.     

Approximation algorithms for dynamic resource allocation

We consider a problem of allocating limited quantities of M types of resources among N independent activities that evolve over T epochs. In each epoch, we assign to each activity a task which consumes resources, generates utility, and determines the subsequent state of the activity. We study the complexity of, and approximation algorithms for, maximizing average utility.     

Inexact proximal point method for general variational inequalities

In this paper, we suggest and analyze a new inexact proximal point method for solving general variational inequalities, which can be considered as an implicit predictor-corrector method. An easily measurable error term is proposed with further relaxed error bound and an optimal step length is obtained by maximizing the profit-function and is dependent on the previous points. Our results include several known and new techniques for solving variational inequalities and related optimization problems. Results obtained in this paper can be viewed as an important improvement and refinement of the previously known results. Preliminary numerical experiments are included to illustrate the advantage and efficiency of the proposed method.