CMA-ES is a powerful method for continuous black-box optimization, in which search is performed by iteratively adapting a multivariate Gaussian distribution. To further improve its performance, mirrored orthogonal sampling (MOS) has been proposed as an advanced sampling technique. In this study, we show that CMA-ES with MOS can suffer from performance degradation on multimodal problems. We identify cumulative step-size adaptation (CSA), the standard step-size adaptation mechanism of CMA-ES, as a major source of this issue. We also confirm that existing bias-correction methods for CSA are insufficient to fully resolve this problem on multimodal landscapes. To address this limitation, we propose introducing two-point step-size adaptation (TPA) into CMA-ES with MOS. We examine two TPA variants: one based on direct value comparison and another on rank differences. Unlike CSA, TPA does not rely on evolution path statistics and is expected to be robust in MOS settings. Experimental results demonstrate that the value-comparison TPA significantly outperforms the rank-based variant and CSA on multimodal problems. Furthermore, it remains competitive on unimodal problems, indicating that the proposed approach provides a robust alternative to CSA for MOS-based CMA-ES.

The exponential natural evolution strategy (xNES) and the covariance matrix adaptation evolution strategy (CMA-ES) are effective for continuous black-box optimization, but their search performance strongly depends on hyperparameters such as population size and learning rates. Learning rate adaptation CMA-ES (LRA-CMA-ES) improves robustness by adapting the learning rates of the mean vector and covariance matrix; however, it converges slowly on ill-conditioned problems and often fails on multimodal problems. We argue that these issues partly arise because LRA-CMA-ES employs a single learning rate for the covariance matrix. This implicitly couples the updates of the distribution's step-size and shape components, ignoring the established principle in standard CMA-ES that these components require decoupled update dynamics. To address this limitation, we propose step-size and shape separated LRA-xNES (S3-LRA-xNES), which separately adapts learning rates for step-size and shape components. Experimental results demonstrate that S3-LRA-xNES achieves faster convergence on ill-conditioned problems and improved success rates on multimodal problems. Notably, S3-LRA-xNES outperforms LRA-CMA-ES by achieving a median 82.4% reduction in function evaluations on ill-conditioned problems and consistently improving or maintaining 100% success rates across 50 trials on multimodal problems, highlighting the effectiveness of fully separated learning rate adaptation in xNES.

Black-box discrete optimization (BB-DO) problems arise in many real-world applications, such as neural architecture search and mathematical model estimation. A key challenge in BB-DO is epistasis among parameters where multiple variables must be modified simultaneously to effectively improve the objective function. Estimation of Distribution Algorithms (EDAs) provide a powerful framework for tackling BB-DO problems. In particular, an EDA leveraging a Variational Autoencoder (VAE) has demonstrated strong performance on relatively low-dimensional problems with epistasis while reducing computational cost. Meanwhile, evolutionary algorithms such as DSMGA-II and P3, which integrate bit-flip-based local search with linkage learning, have shown excellent performance on high-dimensional problems. In this study, we propose a new memetic algorithm that combines VAE-based sampling with local search. The proposed method inherits the strengths of both VAE-based EDAs and local search-based approaches: it effectively handles high-dimensional problems with epistasis among parameters without incurring excessive computational overhead. Experiments on NK landscapes―a challenging benchmark for BB-DO involving epistasis among parameters―demonstrate that our method outperforms state-of-the-art VAE-based EDA methods, as well as leading approaches such as P3 and DSMGA-II.

Multi-objective optimization is crucial in scientific and industrial applications where solutions must balance trade-offs among conflicting objectives. State-of-the-art methods, such as NSGA-III and MOEA/D, can handle many objectives but struggle with coverage issues, particularly in cases involving inverted triangular Pareto fronts or strong nonlinearity. Moreover, NSGA-III often relies on simulated binary crossover, which deteriorates in problems with variable dependencies. In this study, we propose a novel multi-start optimization method that addresses these challenges. Our approach introduces a newly introduced scalarization technique, the Target Point-based Tcheby-cheff Distance (TPTD) method, which significantly improves coverage on problems with inverted triangular Pareto fronts. For efficient multi-start optimization, TPTD leverages a target point defined in the objective space, which plays a critical role in shaping the scalarized function. This is because, if the target points are distributed uniformly, it is expected that single-objective function optimization using TPTD could construct an approximate solution set with good coverage. The positions of the target points are adaptively determined according to the shape of the Pareto front, ensuring improvement in coverage. The proposed method first searches for target points corresponding to objective vectors on the Pareto front boundary using a binary search method and then relocates the target points corresponding to objective vectors within the boundary according to the shape of the boundary. This operation is computationally efficient because the positions of the non-boundary target points are determined in a single relocation. Furthermore, the flexibility of this scalarization allows seamless integration with powerful single-objective optimization methods, such as natural evolution strategies, to efficiently handle variable dependencies. Experimental results on benchmark problems, including those with inverted triangular Pareto fronts, demonstrate that our method outperforms NSGA-II, NSGA-III, and MOEA/D-DE in terms of the Hypervolume indicator. Notably, our approach achieves computational efficiency improvements of up to 474 times over these baselines.

The covariance matrix adaptation evolution strategy (CMA-ES) is one of the most successful methods for solving continuous black-box optimization problems. A practically useful aspect of CMA-ES is that it can be used without hyperparameter tuning. However, the hyperparameter settings still have a considerable impact on performance, especially for difficult tasks, such as solving multimodal or noisy problems. This study comprehensively explores the impact of learning rate on CMA-ES performance and demonstrates the necessity of a small learning rate by considering ordinary differential equations. Thereafter, it discusses the setting of an ideal learning rate. Based on these discussions, we develop a novel learning rate adaptation mechanism for CMA-ES that maintains a constant signal-to-noise ratio. Additionally, we investigate the behavior of CMA-ES with the proposed learning rate adaptation mechanism through numerical experiments and compare the results with those obtained for CMA-ES with a fixed learning rate and with population size adaptation. The results show that CMA-ES with the proposed learning rate adaptation works well for multimodal and/or noisy problems without extremely expensive learning rate tuning.

Social issues are complex, and solving them from a single perspective has other negative effects. We set up various Key Performance Indicators (KPIs), in which balanced measures need to be implemented to achieve KPIs. However, it is not easy to find an effective measure that considers the values of each decision maker because the emphasized criteria for the decision maker may not be clear. Furthermore, in addition to the best per-spective, the decision maker may consider multiple perspectives, such as the next best perspective. In this paper, we propose a method for revealing implicit emphasized criteria for the decision maker on social issues, visualizing multiple perspectives such as the best perspective and the next best perspective of the decision maker, and output multiple perspectives. After the decision maker confirms the effect and influence of the measure, the proposed method generates a distribution, defined as a Goodness distribution, that indicates whether the measure is good or bad. Thus using the Goodness distribution, the method reveals implicit emphasized criteria for the decision maker, visualizes multiple important perspectives for the decision maker, and presents the effective measure.

This paper proposes a reinforcement learning (RL) method based on Natural Evolution Strategies (NES). In RL, an agent learns an action strategy (policy) that maximizes the expected cumulative reward by repeatedly interacting with an environment. Derivative-Free (DFO)-based RL methods search for policy parameters that maximize the expected cumulative reward using DFO methods. Augmented Random Search (ARS) is one of the most promising DFO-based RL methods. ARS reportedly showed competitive results with state-of-the-art RL methods such as PPO and SAC on MuJoCo locomotion tasks. However, we believe that ARS has two problems. The first problem is that the performance of state normalization in ARS could deteriorate in environments with early termination of episodes. The second problem is that ARS has many user parameters sensitive to the performance. We propose a new DFO-based RL method that addresses these two problems. In order to address the first problem of ARS, we propose state normalization taking account of early termination of episodes. In order to reduce the user parameters, we propose to employ Exponential NES (xNES) as a DFO method with three techniques: controlling excessive shrinkage of the step size, fixing the normalized transformation matrix, and the antithetic variates method. Numerical experiments using six MuJoCo locomotion tasks showed that the proposed method outperformed ARS in five tasks and showed almost the same performance in the other task. In particular, the proposed method succeeded in achieving an average reward of about 9,500 while ARS about 6,000 in 400,000 episodes in Humanoid-v4 that is one of the most difficult tasks in the MuJoCo locomotion ones. Furthermore, in the same task, the proposed method reached an average reward of 6,000 about four times faster than ARS.

This paper proposes a new natural evolution strategy (NES) for implicitly constrained black-box function optimization (ICBBFO). ICBBFO problems are known to be a difficult class of problems because its objective function is not given explicitly, and only information about whether a solution is feasible or infeasible is given. FM-NES is one of the most promising methods for ICBBFO problems. FM-NES uses a multivariate Gaussian distribution (MGD) for solution generation and updates the mean vector and covariance matrix of the MGD using the natural gradient method to improve the expected value of the solutions generated from the MGD. However, when FM-NES is applied to ICBBFO problems where the optimal solution exists near or on a constraint boundary, it is observed that the performance of FM-NES deteriorates. We believe that the deterioration is caused by two problems of FM-NES. The first problem is that FM-NES performs many unnecessary updates of the MGD on a constraint boundary near the optimal solution because the MGD repeatedly moves into and out of the infeasible region. The second problem is that the shape reset of the MGD may not work properly, resulting in an increase in the number of evaluations required to find the optimal solution. To address the two problems of FM-NES, we propose the Enhanced Fast Moving Natural Evolution Strategy for Implicit Constraint (eFM-NES-IC). We conducted numerical experiments using ICBBFO benchmark problems and an 8-element standard lens system design problem that is a difficult real-world problem with implicit constraints to show the effectiveness of eFM-NES-IC. As a result, eFM-NES-IC outperformed FM-NES, DX-NES-IC, xNES, xNES with the resampling technique, CMA-ES, and CMA-ES with the resampling technique on all the benchmark problems and the 8-element standard lens system design problem.

In this paper, we propose an off-policy deep reinforcement learning (DRL) method utilizing the average reward criterion. While most existing DRL methods employ the discounted reward criterion, this can potentially lead to a discrepancy between the training objective and performance metrics in continuing tasks, making the average reward criterion a recommended alternative. We introduce RVI-SAC, an extension of the state-of-the-art off-policy DRL method, Soft Actor-Critic (SAC), to the average reward criterion. Our proposal consists of (1) Critic updates based on RVI Q-learning, (2) Actor updates introduced by the average reward soft policy improvement theorem, and (3) automatic adjustment of Reset Cost enabling the average reward reinforcement learning to be applied to tasks with termination. We apply our method to the Gymnasium's Mujoco tasks, a subset of locomotion tasks, and demonstrate that RVI-SAC shows competitive performance compared to existing methods.

This paper proposes a new sequential state and parameter estimation method for nonlinear state-space mod-els, named Robust PF/SNES, taking account of ensembles not covering true states. PF/SNES is one of the most promising methods for sequential estimation of states and parameters and reportedly showed better performance than the augmented particle filter (Augmented PF) and the augmented Merging PF (Augmented MPF) that are widely used. Augmented PF and Augmented MPF are the extended versions of PF and MPF that handle parameters as states. PF/SNES sequentially estimates states and parameters by updating a probability distribution of parameters (a parameter distribution) using the Separable Natural Evolution Strategies (SNES) and an ensemble using PF at each time step. However, once an ensemble does not cover the true state, the subsequent estimation performance of PF/SNES deteriorates. In order to remedy the problem of PF/SNES, if the accuracy of the ensemble is judged to be low before SNES updates the parameter distribution at each time step, Robust PF/SNES searches for a high-accuracy ensemble by DX-NES-IC, which maximizes a likelihood with respect to an observation at the previous time step, taking account of the incomplete observation and the multimodality of the likelihood space. We compare the estimation performance of Robust PF/SNES with that of PF/SNES, Augmented PF, and Augmented MPF in terms of state MSE (Mean Squared Error) and parameter MSE on some benchmark problems with initial ensembles that do not cover the true states. The benchmark problems are the 2-state, 4-parameter estimation problem of the Van der Pol model, the 40-state, 41-parameter estimation problem of the Lorenz96 model, and the 10-state, 1-parameter estimation problems with an unobservable state or a bi-modal likelihood space. As a result, Robust PF/SNES showed the best performance on all the benchmark problems. Robust PF/SNES improved the accuracy by about 51.34 - 34760.94 times in terms of state MSE and 14.96 - 760.34 times in terms of parameter MSE, compared to PF/SNES.

This paper proposes a natural evolution strategy (NES) for mixed-integer black-box optimization (MI-BBO) that appears in real-world problems such as hyperparameter optimization of machine learning and materials design. This problem is difficult to optimize because plateaus where the values do not change appear when the integer variables are relaxed to the continuous ones. CMA-ES w. Margin that addresses the plateaus reportedly showed good performance on MI-BBO benchmark problems. However, it has been observed that the search performance of CMA-ES w. Margin deteriorates when continuous variables contribute more to the objective function value than integer ones. In order to address the problem of CMA-ES w. Margin, we propose Distance-weighted eXponential Natural Evolution Strategy taking account of Implicit Constraint and Integer (DX-NES-ICI). We compare the search performance of DX-NES-ICI with that of CMA-ES w. Margin through numerical experiments. As a result, DX-NES-ICI was up to 3.7 times better than CMA-ES w. Margin in terms of a rate of finding the optimal solutions on benchmark problems where continuous variables contribute more to the objective function value than integer ones. DX-NES-ICI also outperformed CMA-ES w. Margin on problems where CMA-ES w. Margin originally showed good performance.

The covariance matrix adaptation evolution strategy (CMA-ES) is one of the most successful methods for solving black-box continuous optimization problems. One practically useful aspect of the CMA-ES is that it can be used without hyperparameter tuning. However, the hyperparameter settings still have a considerable impact, especially for difficult tasks such as solving multimodal or noisy problems. In this study, we investigate whether the CMA-ES with default population size can solve multimodal and noisy problems. To perform this investigation, we develop a novel learning rate adaptation mechanism for the CMA-ES, such that the learning rate is adapted so as to maintain a constant signal-to-noise ratio. We investigate the behavior of the CMA-ES with the proposed learning rate adaptation mechanism through numerical experiments, and compare the results with those obtained for the CMA-ES with a fixed learning rate. The results demonstrate that, when the proposed learning rate adaptation is used, the CMA-ES with default population size works well on multimodal and/or noisy problems, without the need for extremely expensive learning rate tuning.

In this work, we propose a new variant of natural evolution strategies (NES) for high-dimensional black-box opti-mization problems. The proposed method, CR-FM-NES, extends a recently proposed state-of-the-art NES, Fast Moving Natural Evolution Strategy (FM-NES), in order to be applicable in high-dimensional problems. CR-FM-NES builds on an idea using a restricted representation of a covariance matrix instead of using a full covariance matrix, while inheriting an efficiency of FM-NES. The restricted representation of the covariance matrix enables CR-FM-NES to update parameters of a multivariate normal distribution in linear time and space complexity, which can be applied to high-dimensional problems. Our experimental results reveal that CR-FM-NES does not lose the efficiency of FM-NES, and on the contrary, CR-FM-NES has achieved significant speedup compared to FM-NES on some benchmark problems. Furthermore, our numerical experiments using 200, 600, and 1000-dimensional benchmark problems demonstrate that CR-FM-NES is effective over scalable baseline methods, VD-CMA and Sep-CMA.

This paper presents a natural evolution strategy for implicitly constrained black-box function optimization. The black-box function optimization is challenging because explicit representations of objective functions are not given, and only evaluation values of solutions can be used. In implicitly constrained black-box function problems, constraints are not explicitly given, and only the feasibility of a solution is obtained when the objective function is evaluated. In other words, the amount of constraint violation cannot be obtained, which makes the optimization difficult. Natural Evolution Strategies (NES) is one of the promising frameworks for black-box function optimization. DX-NES is an improved version of xNES which is a promising NES using a multivariate normal distribution as the probability distribution. DX-NES has been reported to show good performance on unconstrained black-box function optimization problems. However, DX-NES has a serious problem in that its performance degrades when applied to implicitly constrained problems. In order to address the problem, we propose DX-NES taking account of Implicit Constraint (DX-NES-IC). In experiments using benchmark problems and a lens system design problem, DX-NES-IC showed better performance than DX-NES, xNES, CMA-ES, and those with the resampling technique in terms of the number of successful trials and that of evaluations, where the resampling technique is a constraint handling method which can be used for implicitly constrained problems.

We propose an evolutionary algorithm that takes account of epistasis among parameters for black-box discrete optimization problems. The black-box discrete optimization (BB-DO) is an important problem that appears in various real-world problems such as hyper-parameter optimization of machine learning and is a difficult class of optimization problems to which optimization methods that require derivative of an objective function cannot be applied. In addition, epistasis among parameters, or the dependencies among variables, makes BB-DO problems more difficult. The bayesian optimization algorithm (BOA) has been proposed as a promising method to address epistasis in BB-DO problems. However, BOA suffers from a serious problem. The problem is that the diversity of a population is likely to be lost. Therefore, BOA requires a large population size for optimization. In order to remedy the problem of BOA, we introduce three schemes to maintain the diversity of the population into BOA. In experiments, we use two benchmark problems, a 3-deceptive function and a NK-landscape, and a structural optimization of neural networks to show the effectiveness of the proposed method. The experimental results showed that the proposed method improved the number of evaluations by 31.5% and the population size by 96.9% in a 180-dimensional 3-deceptive function and found comparable or better solutions in all NK-landscape settings compared to BOA. In the structural optimization of neural networks, the proposed method improved the number of evaluations by 21.3% and the population size by 92.3% compared to BOA. In addition, the proposed method was superior to conventional optimization methods used in this field, ASNG-NAS, regularized evolution, reinforcement learning, TPE, and random search, in terms of the evaluation value.

This paper proposes a new sequential estimation method for simultaneously estimating states and parameters of a state space model. Particle filter (PF) is known as a method that can estimate states in difficult sequential state estimation problems with nonlinearity and non-Gaussianity. PF updates an ensemble consisting of multiple particles representing states of a state space model in order to estimate the true state, based on observation, at each time step. However, when PF estimates not only states but also parameters of the state space model at the same time, it is observed that the estimation accuracy deteriorates. When estimating both states and parameters, PF utilizes particles representing states and particles. In order to overcome the problem of PF, we propose a new method that sequentially estimates states by PF and parameters by the separable natural evolution strategy (SNES). SNES is one of the most powerful black-box function optimization methods. In order to confirm the effectiveness of the proposed method, we compare the performance of the proposed method and that of PF using two nonlinear state space models, the Van der Pol model and the Lorenz model. In the Van der Pol model, the median MSE values of the state and the parameter of the proposed method were 0.003610 and 0.01468 and those of PF were 4.228 and 6.520, respectively. In the Lorenz model, the median MSE values of the state and the parameter of the proposed method were 0.002639 and 0.003479 and those of PF were 309.5 and 1.470, respectively. The smaller MSE is, the better the performance is.

This paper proposes a new particle filter (PF) named the particle filter with extrapolation by crossover (PF-XC) for estimating state vectors of dynamical systems. Estimating state vectors of dynamical systems is one of the most important problems that often appears in the wide area of engineering such as robotics, statistics and marine meteorology. The particle filter with interpolation by crossover (PF-IC) is one of the most promising PFs that overcomes a problem of the original PF. PF-IC interpolates particles to obtain an ensemble with high density around the true state. PF-IC shows better performance than PF especially when the number of particles in an ensemble is small. However, PF-IC has a serious problem in that the performance of PF-IC deteriorates when the ensemble does not cover the true state. We believe that this is because PF-IC cannot create particles around the true state when the ensemble does not cover the true state. In order to remedy the problem of PF-IC, PF-XC extrapolates particles to obtain an expanded ensemble in an isotropic manner that covers the true state. In order to investigate that PF-XC effectively works even if ensembles do not cover true states, we compared the performance of PF-XC and that of PF-IC, PF and the merging particle filter (MPF) which is one of the most famous extensions of PF on two benchmark problems that have nonlinear dynamics models. As the result, we confirmed that PF-XC outperformed PF-IC, PF and MPF. PF-XC showed up to about eight times better performance than that of PF-IC in terms of the median root mean squared error.

In this paper, we propose a new parallel genetic algorithm (GA) with edge assembly crossover (EAX) for the traveling salesman problem (TSP). GA with EAX (GA-EAX) is one of the promising meta-heuristics for TSP and found best-known tours for several well-known 100,000-city scale TSP instances. However, it takes about ten days to execute this GA just one time using the default configuration on the 120,000-city instance [1]. Therefore, it is crucial to reduce the running time of GA-EAX for 100,000-city scale instances in order to make it possible to improve the algorithm through trial and error. The proposed parallel GA achieves about twenty-times speed up without deteriorating the quality of solutions compared to the original GA-EAX. We also demonstrate that the proposed parallel GA successfully finds new best-known tours for the 120,000-city and 180,000-city instances called vangogh120K and courbet180K, respectively.

This paper presents an extended variant of the distance-weighted exponential natural evolution strategy (DXNES) that works well in uncertain environments. Since we often face objective functions with uncertain parameters in real-world problems, function optimization in uncertain environments is an important problem. The covariance matrix adaptation evolution strategy (CMA-ES) and DX-NES have been proposed as promising methods for function optimization in deterministic environments. The performance of these methods, however, deteriorates in uncertain environments. The uncertain handling CMA-ES (TIH-CMA-ES) has been proposed as an extended variant of CMA-ES for uncertain environments and has shown relatively good performance on problems with uncertain parameters. In this paper, we propose an extended variant of DX-NES named DX-NES for uncertain environments (DX-NES-TIE). DX-NES-TIE approximates the objective function by a quadratic function. DXNES-TIE uses approximation function values for updating the mutation distribution if the noise is strong; otherwise it uses observed objective function values. The strength of the noise is quantified by using the approximation function and the evolution path. Through numerical experiments on 20-dimensional uncertain benchmark problems, we demonstrate that DX-NES-TIE can find ten to 2,000 times as accurate solutions as TIH-CMA-ES can. We also apply DX-NES-TIE to 80-dimensional problems and confirm that DX-NES-TIE is scalable with respect to problem dimensionality.

In this paper, we propose a new real-coded genetic algorithm (RCGA) for implicit constrained black-box function optimization. On implicit constrained problems, there often exist active constraints of which the optima lie on the boundaries, which makes the problem more difficult. Almost all of conventional constraint-handling techniques cannot be applied to implicit constrained black-box function optimization because we cannot get quantities of constraint violations and preference order of infeasible solutions. The resampling technique may be the only available choice to handle the implicit constraint. AREX/JGG is one of the most powerful RCGAs for non-constrained problems. However, AREX/JGG with resampling technique deteriorates on implicit constrained problems because few individuals are generated near the boundaries of active constraints and, thus, a population cannot approach the boundaries quickly. In order to find these optima, we believe that it is necessary to locate the mode of a distribution for generating new individuals nearer the boundaries. Since solutions around the optima on boundaries of active constraints may have better evaluation values, our proposed method employs the weighted mean of the best half individuals in a population as the mode of the distribution. We assess the proposed method through experiments with some benchmark problems and the results show the proposed method succeeds in finding the optimum with about 40-85% of function evaluations compared to AREX/JGG with resampling technique.

This paper presents a new evolutionary algorithm for function optimization named the distance-weighted exponential natural evolution strategies (DX-NES). DX-NES remedies two problems of a conventional method, the exponential natural evolution strategies (xNES), that shows good performance when it does not need to move the distribution for sampling individuals down the slope to the optimal point. The first problem of xNES is that the search efficiency deteriorates while the distribution moves down the slope of an ill-scaled function because it degenerates before reaching the optimal point. The second problem is that the settings of learning rates are inappropriate because they do not taking account of some factors affecting the estimate accuracy of the natural gradient. We compared the performance of DX-NES with that of xNES and CMA-ES on typical benchmark functions and confirmed that DX-NES outperformed the xNES on all the benchmark functions and that DX-NES showed better performance than CMA-ES on the almost all functions except the k-tablet function.

In our previous study, we have proposed Adaptive Weighted Aggregation (AWA), a framework of multi-starting optimization methods based on scalarization for solving multi objective function optimization problems. The experiments in the proposal show that AWA outperforms conventional multi starting descent methods at coverage of solutions. However, the suitable termination condition for AWA has not been understood. Coverage of AWA's solutions and computational cost of AWA strongly depends on the termination condition. In this paper, we derive the necessary and sufficient iteration count to achieve high coverage and the number of approximate solutions generated until AWA stops. Numerical experiments show that AWA still achieves better coverage than the conventional methods under the derived termination condition.

Adaptive Weighted Aggregation (AWA) is a frame work of multi-starting optimization methods based on scalarization for solving multiobjective function optimization problems. It progressively generates new solutions to refine the approximation of the Pareto set or the Pareto front by the subdivision, and iteratively estimates the appropriate weight vector for scalarization in each search by the weight adaptation. Our recent study shows that AWA's solution set combinatorially increases for the number of objectives. In this paper, we propose a new subdivision and weight adaptation scheme of AWA to improve its scalability. Numerical experiments show the effectiveness of the proposed method.

In this paper, we propose a new framework taking account of multi-funnel functions for Real-coded Genetic Algorithms (RCGAs). In the continuous function optimization, Evolutionary Algorithms (EAs) are one of the most effective optimization methods. However, most conventional EAs, such as RCGAs and CMA-ES, work efficiently on functions with big-valley landscape and they deteriorate on the multi-funnel functions. Innately Split Model (ISM) has been proposed as a framework of GAs for multi-funnel functions and outperforms conventional GAs on this kind of functions. However, ISM is considered to have two problems in terms of efficiency of the search and difficulty of parameter settings. Our framework repeats a search by RCGAs as ISM does and has two effective mechanisms to remedy the two problems of ISM. We conducted experiments on benchmark functions with multi-funnel and big valley landscapes and our framework outperformed conventional EAs, Multi-start RCGA (MS-RCGA), Multi-start CMA-ES (MS CMA-ES) and ISM, on the multi-funnel functions. Our frame work achieved as good performance as MS-RCGA and MS CMA-ES on the big-valley function where ISM significantly deteriorates.

The multi-starting descent method is a promising approach to unimodal multiobjective function optimization problems because of its precision of obtained solutions. Descent methods can be classified into two categories; the multiobjective descent method directly using the Jacobian matrix of objective functions and the scalarized descent method using the gradient of a scalarized objective function. In the multiobjective descent method and the scalarized descent method, a convergent point depends on an initial solution and a weight vector, respectively. However, it is difficult to choose appropriate initial solutions or weight vectors for obtaining widely and evenly distributed solutions. In order to remedy the problems of the conventional methods, we propose a multi-starting scalarized descent method named AWA that employs the Chebyshev norm method as a scalarization method and an adaptive scheme of weight vectors for the scalarization method. We show the effectiveness of the proposed method through some experiments.

Real-Coded Genetic Algorithms (RCGAs) have been extensively studied for last two decades because RCGAs have advantages over conventional continuous function optimization methods when multimodal functions are optimized. Innately Split Model (ISM) is one of promising approaches to enhance RCGAs where a set of population groups are evolved in parallel and groups are re-initialized if two groups searches a similar region (it is called redundant searches). In this paper, we propose a new strategy for the re-initialization of groups to improve the performance of ISM. In our method, redundant searches are detected by using the information of the search histories of the groups. This information is called traps and is stored as a set of hyper-ellipsoids representing the distributions of the previous groups. We demonstrate that the proposed method is robust and superior to the original ISM.

This paper investigates theoretically the convergence properties of the stochastic algorithms of a class including both CMAESs and EDAs on constrained minimization of continuously differentiable functions. We are interested in algorithms that do not get stuck on a slope of the function, but converge only to local optimal points. Convergence to a point that is neither a stationary point of the function nor a boundary point is evidence that the convergence properties are not well behaved. We investigate what properties are necessary/sufficient for the algorithm to avoid this type of behavior, i.e., what properties are necessary for the algorithm to converge only to local optimal points of the function. We also investigate the analogous conditions on the parameters of two variants of modern EC-based stochastic algorithms, namely, a CMAES employing rank-μ update and an EDA known as EMNAglobal. The comparison between the apparently similar two systems shows that they have significantly different theoretical behaviors. This result presents us with an insight into the way we design well-behaved optimization algorithms.

In this paper, we propose an efficient algorithm for estimating the natural policy gradient with parameter-based exploration; this algorithm samples directly in the parameter space. Unlike previous methods based on natural gradients, our algorithm calculates the natural policy gradient using the inverse of the exact Fisher information matrix. The computational cost of this algorithm is equal to that of conventional policy gradients whereas previous natural policy gradient methods have a prohibitive computational cost. Experimental results show that the proposed method outperforms several policy gradient methods.

The purpose of this paper is to propose a new real-coded genetic algorithm (RCGA) named Networked Genetic Algorithm (NGA) that intends to find multiple optima simultaneously in deceptive globally multimodal landscapes. Most current techniques such as niching for finding multiple optima take into account big valley landscapes or non-deceptive globally multimodal landscapes but not deceptive ones called UV-landscapes. Adaptive Neighboring Search (ANS) is a promising approach for finding multiple optima in UV-landscapes. ANS utilizes a restricted mating scheme with a crossover-like mutation in order to find optima in deceptive globally multimodal landscapes. However, ANS has a fundamental problem that it does not find all the optima simultaneously in many cases. NGA overcomes the problem by an adaptive parent-selection scheme and an improved crossover-like mutation. We show the effectiveness of NGA over ANS in terms of the number of detected optima in a single run on Fletcher and Powell functions as benchmark problems that are known to have UV-landscapes. We also analyze the behavior of NGA to confirm that the adaptive parent-selection scheme contributes the performance of NGA.

Premature convergence is one of the most notable obstacles that GAs face with. Once it happens, GAs cannot generate candidate solutions globally and the solutions are finally captured by local minima. To overcome it, we propose a mechanism that indirectly controls the variety of the population. It is realized by adapting the expansion rate parameter of crossovers, which determines the variance of the crossover distribution. The resulting algorithm is called adaptation of expansion rate (AER). The performance of the proposed methods is compared to an existing GA on several benchmark functions including functions whose landscape have ridge or multimodal structure. On these functions, existing GAs are likely to lead to premature convergence. The experimental result shows our approach outperforms the existing one on deceptive functions without disturbing the performance on comparatively easy problems.

This paper aims the design of efficient and effective optimization algorithms for function optimization. This paper presents a new framework of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Recent studies modified the CMA-ES from the viewpoint of covariance matrix adaptation and resulted in drastic reduction of the number of generations. In addition to their modification, this paper modifies the CMA-ES from the viewpoint of step size adaptation. The main idea of modification is semantically specializing functions of covariance matrix adaptation and step size adaptation. This new method is evaluated on 8 classical unimodal and multimodal test functions and the performance is compared with standard CMA-ES. The experimental result demonstrates an improvement of the search performances in particular with large populations. This result is mainly because the proposed Hybrid-SSA instead of the existing CSA can adjust the global step length more appropriately under large populations and function specialization helps appropriate adaptation of the overall variance of the mutation distribution.

Although multi-objective GA (MOGA) is an efficient multi-objective optimization (MOO) method, it has some limitations that need to be tackled, which include unguaranteed uniformity of solutions and uncertain finding of periphery of Pareto-optimal solutions. It has been shown that, on bi-objective problems, which are the subject of this paper, local Pareto-optimal solutions form curves. In this case, some of the limitations of MOGA can be resolved by sampling the curves uniformly in the variable space and in the objective space. This paper proposes Pareto Path Following (PPF) which does the sampling by extending the framework of Numerical Path Following, verifies that PPF exhibits the desired behaviors, and addresses the extension of PPF for problems with more than two objective functions.Application of PPF is not limited to refinement of solutions obtained with MOGA. PPF makes it natural to have a local Pareto-optimal solution curve as the unit of search, which leads to curve-based MOGA. PPF also enables examination of which Pareto-optimal solution curves are found by MOO methods, and performance metrics based on it can be defined. This paper proposes these applications of PPF in MOGA and compares standard MOGA and curve-based MOGA using the metrics to reveal their characteristics.

This paper describes a GA based lazy approach toward reinforcement learning. This approach employs data-driven policy, which is composed of an instance set and an instance-based action selector. This feature provides a number of advantages. However some difficulties remain uninvestigated. One of them is the huge and complicated search space. We have an idea that preserving characteristics of the GA population and introducing new characteristics can overcome these difficulties. On the basis of this idea, we propose two genetic operators; Binomial Distribution Crossover (BDX) and iterated refreshment. The BDX generates the descendants inheriting the parents’ characteristics and the iterated refreshment introduces new characteristics greedily. The GA powered by these operators was applied to the benchmark tasks to demonstrate the ability. Each operator also was investigated and discussed from the various perspectives. Finally, we provide the preferable parameter settings for our method.

The function optimization is one of the most important optimization problems. In approaches to function optimization by evolutionary computation, a real-coded genetic algorithm, UNDX+MGG, shows good performance on multimodal functions with epistasis among parameters. However, UNDX+MGG has a problem that its performance is good on functions with big valley structures but deteriorates on those with the UV structures. On the other hand, ISM shows good performance on functions with the UV structures. However, ISM has two problems that 1) it fails in search when the region of the V valley including the optimum is very narrow and 2) its performance deteriorates on functions with big valley structures. In this paper, we propose a new evolutionary algorithm that aims at overcoming the problems of UNDX+MGG and ISM and examine its effectiveness through some experiments.

Nuclear magnetic resonance (NMR) spectroscopy is a promising technique for the three-dimensional structure determination of proteins that is one of the most important problems in post-sequence era. This technique has a serious problem that it takes several months for an expert to analyze the data of only one protein. In order to remedy the problem, Ono et al. (2002) have proposed an automatic method based on a genetic algorithm (GA) for analyzing the data and determining the three-dimensional structures of proteins and reported that they had good results on relatively small-scale problems. In this paper, to get good results on larger-scale problems, we propose a new initial population generation method and the substructure exchange crossover (SSXX) that inherits substructures as characters from parents to offspring. In order to examine the effectiveness of the proposed method, we perform some experiments.

We improve network-structure-search evolutionary algorithm (NSS-EA) that is a search method for inference of genetic networks by S-system. Search methods for inference of genetic networks by S-system should meet the following requirements: 1) efficient search of a set of satisfactory structures; 2) search of structures satisfying biological knowledge; and 3) search of the true structure, NSS-EA is an excellent method from the viewpoints of Requirement 1 and 2. However, it has a problem from the viewpoint of Requirement 3. In order to solve this problem, first, we improve the parameter search process by using the time course data of disrupted strains as well as that of a wild type when evaluating genetic networks. Second, we propose four new structure-search operators taking account of mutual interactions among substances. We show the effectiveness of the proposed improvements for NSS-EA from the viewpoint of Requirement 3 by comparing the performance of the original NSS-EA and the improved NSS-EA on a five-substance benchmark problem.

In this paper, we propose a framework for enabling for researchers of genetic algorithms (GAs) to easily develop GAs running on the grid, named "grid-oriented genetic algorithms (GOGAs)", and actually "gridify" a GA for estimating genetic networks, which is being developed by our group, in order to examine usability of the proposed GOGA framework. We also evaluate the scalability of the "gridified" GA by applying it to a five-gene genetic network estimation problem on a grid testbed constructed in our laboratory.

This paper presents the network-structure search evolutionary algorithm (NSS-EA) for inference of genetic networks by S-systems. NSS-EA efficiently finds multiple different network structures which explain gene-expression time-course data observed in biological experiments. In inference of genetic networks by S-system, we are required to find as many network structures that explain experimentally-observed data as possible. This is because, in general, it is difficult to obtain sufficient time-course data by which we can determine a network structure uniquely. A network structure is determined by whether each system parameter of its S-system is positive, negative or zero. Tominaga et al. and Ueda et al. have proposed methods that repeatedly run real-coded genetic algorithms (GAs) for searching the system parameters of S-system with different random number series in each GA run to obtain multiple different network structures. These methods have two serious problems that the same network structures can be repeatedly found in multiple GA runs and that a biological knowledge that the number of substances interacting with one substance is relatively small is not taken into account. This is because how many and what kind of structures are found by real-coded GAs depend on the random number series used by the Gas. In this paper, we try to solve the above problems by explicitly separating the process of searching network structure, i.e. searching the signs of system parameters of S-system, and that of searching the values of the system parameters. Through some numerical experiments, we show that the proposed method, NSS-EA, can efficiently find more different kinds of network structures than the conventional methods.

Most conventional genetic algorithms (GAs) for function optimization always search all parameters simultaneously. As the result, the search space size increases exponentially with the number of parameters. Therefore, the search efficiency of these GAs deteriorates in high-dimensional function optimization because they requires a huge population size and enormous computation time. Generally, in order to find the optima, if a parameter has no interaction with the others, it can be searched independently and, if it has interactions with others, it must be searched with the ones which have interactions with it. We believe that, in many cases, all parameters do not need to be searched simultaneously because many evaluation functions in real-world applications have partially epistasis. We propose a new genetic hill climbing method. The proposed method, first, estimates all interactions among parameters and, then, incrementally improves a search point, using a neighborhood that is a subspace spaned by a parameter and the parameters having interactions with it, named epistasis neighborhood. The sampling method in an epistasis neighborhood is UNDX+MGG, which is a real-coded GA showing good performance on epistatic multimodal functions. We confirm that the proposed method shows better performance than conventional GAs on high-dimensional partially-epistatic functions by applying them to some benchmark problems.

Protein three-dimensional structure determination is one of the most important problems in molecular biology. Nuclear magnetic resonance (NMR) spectroscopy is one of the promising techniques capable of determining the three-dimensional structures of proteins at atomic resolution. In determining protein structures using NMR spectroscopy, nuclear Overhauser effect (NOE) signal assignment is the most laborious and time-consuming process. Attempts to automate NOE signal assignment have failed so far. In this paper, we propose a new automatic assignment method of NOE signals based on a real-coded genetic algorithm and examine its effectiveness by applying it to determining the structure of an /spl alpha/-helix, which is a well-known common substructure of proteins, and a protein called HMG2B.

Power plant start-up scheduling is aimed at minimizing the start-up time while limiting maximum turbine rotor stresses. This scheduling problem is highly nonlinear and has a number of local optima. In our previous research, we proposed an efficient search model: genetic algorithms (GAs) with enforcement operation to focus the search along the edge of the feasible space where the optimal schedule is supposed to stay. Based on a nonlinear dynamic simulation and a linear inverse calculation with the iteration method, the enforcement operation is applied to move schedules generated by GA toward the edge. We prove that the optimal schedule lies on the edge, ensuring that searching along the edge instead of the entire space can improve the search efficiency significantly without missing the optimum. Furthermore, we provide a theoretical setting equation for the inverse enforcement gains of the linear inverse calculation, intended to move schedules closer to the edge at each iteration of the enforcement operation. The theoretical setting equation is verified and discussed with the test results. We propose the theoretical setting equation with the test results as a guideline for the use of our proposed search model: GA with enforcement operation.

The Neuro-Evolution (NE), the training of neural networks with genetic algorithms (GAs), has received much attention as one of the reinforcement learning techniques that can let agents learn appropriate policies, i.e. mappings from sensory inputs to action outputs, in environments with delayed rewards. Although several studies on NE systems have been made so far, there are no studies that take account of epistasis among weight parameters in training neural networks with GAs. In function optimization, epistasis among parameters is one of the important features which make functions difficult to be optimized. Epistasis among parameters has to be considered in order to successfully optimize difficult functions with large number of parameters to be determined. In this paper, we present an NE system based on a real-coded GA using the Unimodal Normal Distribution Crossover (UNDX). The UNDX shows excellent performance in optimizing functions with strong epistasis among parameters. The NE system based on the UNDX are applied to some benchmark problems, which are more difficult than those used in previous work. The results suggest that epistasis among weight parameters should be considered when we train neural networks for difficult tasks by NE systems.

The unimodal normal distribution crossover (UNDX) for the real-coded genetic algorithms (RCGA) proposed by Ono et al. (1997, 1998) shows an excellent performance in optimization problems of multi-modal and highly epistatic fitness functions in continuous search space. Further, theoretical analysis of the UNDX shows that the UNDX is a crossover operator that preserves the statistics such as the mean vector and the covariance matrix of the population well. The present paper proposes some design guidelines for crossover operators for RCGA. Then, based on these guidelines, a multi-parental extension of the UNDX is proposed so as to enhance its exploration ability. Performance of the extended UNDX is evaluated by numerical experiments.

Power plant start-up scheduling is aimed at minimizing the start-up time while limiting maximum turbine-rotor stresses. A shorter start-up time not only reduces fuel and electricity consumption during the start-up process, but also increases its capability of adapting to changes in electricity demand. The start-up scheduling problem can be formulated as a function optimization problem with constraints. We have constructed an efficient and robust search model-a genetic algorithm (GA) with an enforcement operation-which forces the search along the edge of the feasible space, where the optimal schedule is supposed to exist. However, this model has to perform a prior Monte Carlo test to obtain the enforcement gains used for the implementation of the enforcement operation. In this paper, we attempt to eliminate the Monte Carlo test by proposing a self-reliant search model by introducing a GA with an adaptive enforcement operation that can generate and adapt enforcement gains during the search process. The test results of this proposed model show that the overall number of time-consuming dynamic simulations for the constraints calculation can be reduced further, thus increasing the overall efficiency of finding the optimal or near-optimal schedules.