Two-agent Pareto optimal cooperative investment in general semimartingale model

We consider the problem of expected utility maximization for the two-agent case in general semimartingale model. For this case a cooperative investment game is posed as follows: firstly collect both agents' capital as a whole at the initial time, and invest it in a trading strategy. Then at some time T ₀ one agent quits cooperation and terminates investment, so they divide the wealth and each of them gets a part. During the time interval [T ₀, T], the other agent invests her capital in a new trading strategy herself. By stochastic optimization methods with the help of the theory of backward stochastic differential equations, we give a characterization of Pareto optimal cooperative strategies and a characterization of situations where cooperation strictly Pareto dominates non-cooperation in our model.     

Parallelization Strategies for Rollout Algorithms

Rollout algorithms are innovative methods, recently proposed by Bertsekas et al. [3], for solving NP-hard combinatorial optimization problems. The main advantage of these approaches is related to their capability of magnifying the effectiveness of any given heuristic algorithm. However, one of the main limitations of rollout algorithms in solving large-scale problems is represented by their computational complexity. Innovative versions of rollout algorithms, aimed at reducing the computational complexity in sequential environments, have been proposed in our previous work [9]. In this paper, we show that a further reduction can be accomplished by using parallel technologies. Indeed, rollout algorithms have very appealing characteristics that make them suitable for efficient and effective implementations in parallel environments, thus extending their range of relevant practical applications.We propose two strategies for parallelizing rollout algorithms and we analyze their performance by considering a shared-memory paradigm. The computational experiments have been carried out on a SGI Origin 2000 with 8 processors, by considering two classical combinatorial optimization problems. The numerical results show that a good reduction of the execution time can be obtained by exploiting parallel computing systems.     

Memetic cooperative models for the tool switching problem

This work deals with memetic-computing agent-models based on the cooperative integration of search agents endowed with (possibly different) optimization strategies, in particular memetic algorithms. As a proof-of-concept of the model, we deploy it on the tool switching problem (ToSP), a hard combinatorial optimization problem that arises in the area of flexible manufacturing. The ToSP has been tackled by different algorithmic methods ranging from exact to heuristic methods (including local search meta-heuristics, population-based techniques and hybrids thereof, i.e., memetic algorithms). Here we consider an ample number of instances of this cooperative memetic model, whose agents are adapted to cope with this problem. A detailed experimental analysis shows that the meta-models promoting the cooperation among memetic algorithms provide the best overall results compared with their constituent parts (i.e., memetic algorithms and local search approaches). In addition, a parameter sensitivity analysis of the meta-models is developed in order to understand the interplay among the elements of the proposed topologies.     

Théorèmes d'existence pour un modèle membranaire « proprement invariantde plaque non linéairement élastique

We establish the “local” existence of an injective solution to the nonlinear, “properly invariant”, membrane plate model, stated in [1] and [2], successively for the clamped plate submitted to forces parallel to its plane and for the plate submitted to a boundary condition of place of “extended” state.     

Stochastic Pareto local search: Pareto neighbourhood exploration and perturbation strategies

Pareto local search (PLS) methods are local search algorithms for multi-objective combinatorial optimization problems based on the Pareto dominance criterion. PLS explores the Pareto neighbourhood of a set of non-dominated solutions until it reaches a local optimal Pareto front. In this paper, we discuss and analyse three different Pareto neighbourhood exploration strategies: best, first, and neutral improvement. Furthermore, we introduce a deactivation mechanism that restarts PLS from an archive of solutions rather than from a single solution in order to avoid the exploration of already explored regions. To escape from a local optimal solution set we apply stochastic perturbation strategies, leading to stochastic Pareto local search algorithms (SPLS). We consider two perturbation strategies: mutation and path-guided mutation. While the former is unbiased, the latter is biased towards preserving common substructures between 2 solutions. We apply SPLS on a set of large, correlated bi-objective quadratic assignment problems (bQAPs) and observe that SPLS significantly outperforms multi-start PLS. We investigate the reason of this performance gain by studying the fitness landscape structure of the bQAPs using random walks. The best performing method uses the stochastic perturbation algorithms, the first improvement Pareto neigborhood exploration and the deactivation technique.     

Performance evaluation of evolutionary class of algorithms—An application to 0–1 knapsack problem

The 0–1 knapsack [1] problem is a well-known NP-complete problem. There are different algorithms in the literature to attack this problem, two of them being of specific interest. One is a pseudo polynomial algorithm of order O(nK), K being the target of the problem. This algorithm works unsatisfactorily, as the given target becomes high. In fact, the complexity might become exponential in that case. The other scheme is a fully polynomial time approximation scheme (FPTAS) whose complexity is also polynomial time. The present paper suggests a probabilistic heuristic which is an evolutionary scheme accompanied by the necessary statistical formulation and its theoretical justification. We have identified parameters responsible for the performance of our evolutionary scheme which in turn would keep the option open for improving the scheme.     

Topological dynamics for multidimensional perturbations of maps with covering relations and Liapunov condition

In this paper, we study topological dynamics of high-dimensional systems which are perturbed from a continuous map on Rm×Rk of the form (f(x),g(x,y)). Assume that f has covering relations determined by a transition matrix A. If g is locally trapping, we show that any small C⁰ perturbed system has a compact positively invariant set restricted to which the system is topologically semi-conjugate to the one-sided subshift of finite type induced by A. In addition, if the covering relations satisfy a strong Liapunov condition and g is a contraction, we show that any small C¹ perturbed homeomorphism has a compact invariant set restricted to which the system is topologically conjugate to the two-sided subshift of finite type induced by A. Some other results about multidimensional perturbations of f are also obtained. The strong Liapunov condition for covering relations is adapted with modification from the cone condition in Zgliczyński (2009) [11]. Our results extend those in Juang et al. (2008) [1], Li et al. (2008) [2], Li and Malkin (2006) [3], Misiurewicz and Zgliczyński (2001) [4] by considering a larger class of maps f and their multidimensional perturbations, and by concluding conjugacy rather than entropy. Our results are applicable to both the logistic and Hénon families.     

On homotopy groups of quandle spaces and the quandle homotopy invariant of links

For a quandle X, the quandle space BX is defined, modifying the rack space of Fenn, Rourke and Sanderson (1995) [13], and the quandle homotopy invariant of links is defined in Z[π₂(BX)], modifying the rack homotopy invariant of Fenn, Rourke and Sanderson (1995) [13]. It is known that the cocycle invariants introduced in Carter et al. (2005) [3], Carter et al. (2003) [5], Carter et al. (2001) [6] can be derived from the quandle homotopy invariant.In this paper, we show that, for a finite quandle X, π₂(BX) is finitely generated, and that, for a connected finite quandle X, π₂(BX) is finite. It follows that the space spanned by cocycle invariants for a finite quandle is finitely generated. Further, we calculate π₂(BX) for some concrete quandles. From the calculation, all cocycle invariants for those quandles are concretely presented. Moreover, we show formulas of the quandle homotopy invariant for connected sum of knots and for the mirror image of links.     

Novel biogeography-based optimization algorithm with hybrid migration and global-best Gaussian mutation

The Biogeography-Based Optimization algorithm and its variants have been used widely for optimization problems. To get better performance, a novel Biogeography-Based Optimization algorithm with Hybrid migration and global-best Gaussian mutation is proposed in this paper. Firstly, a linearly dynamic random heuristic crossover strategy and an exponentially dynamic random differential mutation one are presented to form a hybrid migration operator, and the former is used to get stronger local search ability and the latter strengthen the global search ability. Secondly, a new global-best Gaussian mutation operator is put forward to balance exploration and exploitation better. Finally, a random opposition learning strategy is merged to avoid getting stuck in local optima. The experiments on the classical benchmark functions and the complexity functions from CEC-2013 and CEC-2017 test sets, and the Wilcoxon, Bonferroni-Holm and Friedman statistical tests are used to evaluate our algorithm. The results show that our algorithm obtains better performance and faster running speed compared with quite a few state-of-the-art competitive algorithms. In addition, experimental results on Minimum Spanning Tree and K-means clustering optimization show that our algorithm can cope with these two problems better than the comparison algorithms.     

Cognitive learning in differential evolution and its application to model order reduction problem for single-input single-output systems

Differential evolution (DE) is a well known and simple population based probabilistic approach for global optimization over continuous spaces. It has reportedly outperformed a few evolutionary algorithms and other search heuristics like the particle swarm optimization when tested over both benchmark and real world problems. DE, like other probabilistic optimization algorithms, has inherent drawback of premature convergence and stagnation. Therefore, in order to find a trade-off between exploration and exploitation capability of DE algorithm, a new parameter namely, cognitive learning factor (CLF) is introduced in the mutation process. Cognitive learning is a powerful mechanism that adjust the current position of individuals by the means of some specified knowledge (previous experience of individuals). The proposed strategy is named as cognitive learning in differential evolution (CLDE). To prove the efficiency of various approaches of CLF in DE,?CLDE is tested over 25 benchmark problems. Further, to establish the wide applicability of CLF,?CLDE is applied to two advanced DE variants. CLDE is also applied to solve a well known electrical engineering problem called model order reduction problem for single input single output systems.     

Multi-wave algorithms for metaheuristic optimization

We propose new iterated improvement neighborhood search algorithms for metaheuristic optimization by exploiting notions of conditional influence within a strategic oscillation framework. These approaches, which are unified within a class of methods called multi-wave algorithms, offer further refinements by memory based strategies that draw on the concept of persistent attractiveness. Our algorithms provide new forms of both neighborhood search methods and multi-start methods, and are readily embodied within evolutionary algorithms and memetic algorithms by solution combination mechanisms derived from path relinking. These methods can also be used to enhance branching strategies for mixed integer programming.     

Fitness landscape analysis for the no-wait flow-shop scheduling problem

The fitness landscape of the no-wait (continuous) flow-shop scheduling problem is investigated by examining the ruggedness of the landscape and the correlation between the quality of a solution and its distance to an optimal solution. The results confirm the presence of a big valley structure as known from other combinatorial optimization problems. The suitability of the landscape for search with evolutionary computation and local search methods is discussed. The observations are validated by experiments with two evolutionary algorithms.     

Structural heterogeneity mediates the effect of community structure on cooperation

Emergence of cooperation in evolutionary prisoner's dilemma game strongly depends on the topology of underlying interaction network. We explore this dependence using community networks with different levels of structural heterogeneity, which are generated by a tunable upper‐bound on the total number of links that any vertex can have. We study the effect of community structure on cooperation by analyzing a finite population analogue of the evolutionary replicator dynamics. We find that structural heterogeneity mediates the effect of community structure on cooperation. In the community networks with low level of structural heterogeneity, community structure has negative effect on cooperation. However, the positive effect of community structure on cooperation appears and enhances with increasing structural heterogeneity. Our work may be helpful for understanding the complexity of cooperative behaviors in social networks. © 2011 Wiley Periodicals, Inc. Complexity, 2012     

Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems

We present two strategies for warmstarting primal-dual interior point methods for the homogeneous self-dual model when applied to mixed linear and quadratic conic optimization problems. Common to both strategies is their use of only the final (optimal) iterate of the initial problem and their negligible computational cost. This is a major advantage when compared to previously suggested strategies that require a pool of iterates from the solution process of the initial problem. Consequently our strategies are better suited for users who use optimization algorithms as black-box routines which usually only output the final solution. Our two strategies differ in that one assumes knowledge only of the final primal solution while the other assumes the availability of both primal and dual solutions. We analyze the strategies and deduce conditions under which they result in improved theoretical worst-case complexity. We present extensive computational results showing work reductions when warmstarting compared to coldstarting in the range 30–75% depending on the problem class and magnitude of the problem perturbation. The computational experiments thus substantiate that the warmstarting strategies are useful in practice.     

Landscape analysis and efficient metaheuristics for solving the n-queens problem

The n-queens problem is a classical combinatorial optimization problem which has been proved to be NP-hard. The goal is to place n non-attacking queens on an n×n chessboard. In this paper, two single-solution-based (Local Search (LS) and Tuned Simulated Annealing (SA)) and two population-based metaheuristics (two versions of Scatter Search (SS)) are presented for solving the problem. Since parameters of heuristic and metaheuristic algorithms have great influence on their performance, a TOPSIS-Taguchi based parameter tuning method is proposed, which not only considers the number of fitness function evaluations, but also aims to minimize the runtime of the presented metaheuristics. The performance of the suggested approaches was investigated through computational analyses, which showed that the Local Search method outperformed the other two algorithms in terms of average runtimes and average number of fitness function evaluations. The LS was also compared to the Cooperative PSO (CPSO) and SA algorithms, which are currently the best algorithms in the literature for finding the first solution to the n-queens problem, and the results showed that the average fitness function evaluation of the LS is approximately 21 and 8 times less than that of SA and CPSO, respectively. Also, a fitness analysis of landscape for the n-queens problem was conducted which indicated that the distribution of local optima is uniformly random and scattered over the search space. The landscape is rugged and there is no significant correlation between fitness and distance of solutions, and so a local search heuristic can search a rugged plain landscape effectively and find a solution quickly. As a result, it was statistically and analytically proved that single-solution-based metaheuristics outperform population-based metaheuristics in finding the first solution of the n-queens problem.     

Bounding the beta invariant of 3-connected matroids

The beta invariant is related to the Chromatic and Tutte Polynomials and has been studied by Crapo [4], Brylawski [2], Oxley [7] and others. Crapo [4] showed that a matroid with at least two elements is connected if and only if its beta invariant is greater than zero. Brylawski [2] showed that a connected matroid has beta invariant one if and only if M is isomorphic to a serial-parallel network. Oxley [7] characterized all matroids with beta invariant two, three and four. In this paper, we first give a best possible lower bound on the beta invariant of 3-connected matroids, then we characterize all 3-connected matroids attaining the lower bound. We also characterize all binary matroids with beta invariant 5, 6, and 7.     

Combining VNS with constraint programming for solving anytime optimization problems

This paper presents an hybrid search method for solving on-line optimization problems that are modelled using the vcspValued Constraint Satisfaction Problems framework. To each constraint is associated a valuation representing the “cost to pay” when this constraint will be violated by a solution. Our method (VNS/LDS+CP) uses principles of VNS (Variable Neighborhood Search) and combines a partial tree search (Limited Discrepancy Search) with Constraint Propagation in order to compute local optima. Experiments on the CELAR benchmarks demonstrate significant improvements on other competing methods: LNS/CP/GR [Lobjois, L., Lemaitre, M., Verfaillie, G., 2000. Large neighbourhood search using constraint propagation and greedy reconstruction for valued csp resolution. In: Proceedings of the ECAI2000 Workshop on Modelling and Solving Problems with Constraints], another hybrid method using vcsps, and two standard versions of Simulated-Annealing [Li, Y.H., 1997. Directed annealing search in constraint satisfaction and optimization. Ph.D. thesis, Imperial College of Science, Department of Computing]: Quick and Medium. Moreover, VNS/LDS+CP clearly satisfies the key properties of anytime algorithms. Finally, VNS/LDS+CP has been successfully applied to a real-life on-line resource allocation problem in computer networks.     

Parallel multiobjective evolutionary algorithms for batch scheduling in heterogeneous computing and grid systems

This article presents six parallel multiobjective evolutionary algorithms applied to solve the scheduling problem in distributed heterogeneous computing and grid systems. The studied evolutionary algorithms follow an explicit multiobjective approach to tackle the simultaneous optimization of a system-related (i.e. makespan) and a user-related (i.e. flowtime) objectives. Parallel models of the proposed methods are developed in order to efficiently solve the problem. The experimental analysis demonstrates that the proposed evolutionary algorithms are able to efficiently compute accurate results when solving standard and new large problem instances. The best of the proposed methods outperforms both deterministic scheduling heuristics and single-objective evolutionary methods previously applied to the problem.     

Shifting algorithms for tree partitioning with general weighting functions

Recently two shifting algorithms were designed for two optimum tree partitioning problems: The problem of max-min q-partition [4] and the problem of min-max q-partition [1]. In this work we investigate the applicability of these two algorithms to max-min and min-max partitioning of a tree for various different weighting functions. We define the families of basic and invariant weighting functions. It is shown that the first shifting algorithm yields a max-min q-partition for every basic weighting function. The second shifting algorithm yields a min-max q-partition for every invariant weighting function. In addition a modification of the second algorithm yields a min-max q-partition for the noninvariant diameter weighting function.