著者

永田 裕一 小林 重信

出版者

社団法人人工知能学会

雑誌

人工知能学会誌 (ISSN:09128085)

巻号頁・発行日

vol.14, no.5, pp.848-859, 1999-09-01

被引用文献数

21

---

In this paper, we propose a new crossover named Edge Assembly Crossover(EAX) for the Traveling Salesman Problern. EAX constructs intermediate individuals by assembling only edges of parents under the assignment relaxation that is one of TSP relaxations, and then modifies them into complete ones to satisfy the original constraint of TSP. EAX has two features. One is that EAX is excellent in chartacteristic preservation in view of preserving edges from parents to children. The other is that EAX can generate a wide variety of children from a pair of parents. We show by experiments that EAX generates new soltution candidates under a suitable trade-off between characteristic preservation and a variety of children, which brings better performance than other crossovers do. Finally, we show that EAX realizes global neighborhood search by comparing EAX with the traditional local search operators for TSP.

著者

益富 和之 永田 裕一 小野 功

出版者

進化計算学会

雑誌

進化計算学会論文誌 (ISSN:21857385)

巻号頁・発行日

vol.6, no.1, pp.1-12, 2015 (Released:2015-04-28)

参考文献数

28

---

This paper proposes a novel evolution strategy for noisy function optimization. We consider minimization of the expectation of a continuous domain function with stochastic parameters. The proposed method is an extended variant of distance-weighted exponential evolution strategy (DX-NES), which is a state-of-the-art algorithm for deterministic function optimization. We name it DX-NES for uncertain environments (DX-NES-UE). DX-NES-UE estimates the objective function by a quadratic surrogate function. In order to make a balance between speed and accuracy, DX-NES-UE uses surrogate function values when the noise is strong; otherwise it uses observed objective function values. We conduct numerical experiments on 20-dimensional benchmark problems to compare the performance of DX-NES-UE and that of uncertainty handling covariance matrix adaptation evolution strategy (UH-CMA-ES). UH-CMA-ES is one of the most promising methods for noisy function optimization. Benchmark problems include a multimodal function, ill-scaled functions and a non-C2 function with additive noise and decision variable perturbation (sometime called actuator noise). The experiments show that DX-NES-UE requires about 1/100 times as many observations as UH-CMA-ES does on well-scaled functions. The performance difference is greater on ill-scaled functions.

著者

上村 健人 木下 峻一 永田 裕一 小林 重信 小野 功

出版者

進化計算学会

雑誌

進化計算学会論文誌 (ISSN:21857385)

巻号頁・発行日

vol.4, no.1, pp.1-12, 2013 (Released:2013-03-02)

参考文献数

18

被引用文献数

1

---

This paper proposes a new framework of real-coded genetic algorithms (RCGAs) for the multi-funnel function optimization. The RCGA is one of the most powerful function optimization methods. Most conventional RCGAs work effectively on the single-funnel function that consists of a single big-valley. However, it is reported that they show poor performance or, sometimes, fail to find the optimum on the multi-funnel function that consists of multiple big-valleys. In order to remedy this deterioration, Innately Split Model (ISM) has been proposed as a framework of RCGAs. ISM initializes an RCGA in a small region and repeats a search with the RCGA as changing the position of the region randomly. ISM outperforms conventional RCGAs on the multi-funnel functions. However, ISM has two problems in terms of the search efficiency and the difficulty of setting parameters. Our proposed method, Big-valley Explorer (BE), is a framework of RCGAs like ISM and it has two novel mechanisms to overcome these problems, the big-valley estimation mechanism and the adaptive initialization mechanism. Once the RCGA finishes a search, the big-valley estimation mechanism estimates a big-valley that the RCGA already explored and removes the region from the search space to prevent the RCGA from searching the same big-valley many times. After that, the adaptive initialization mechanism initializes the RCGA in a wide unexplored region adaptively to find unexplored big-valleys. We evaluate BE through some numerical experiments with both single-funnel and multi-funnel benchmark functions.

著者

福島 信純 永田 裕一 小林 重信 小野 功

出版者

進化計算学会

雑誌

進化計算学会論文誌 (ISSN:21857385)

巻号頁・発行日

vol.4, no.2, pp.57-73, 2013 (Released:2013-09-11)

参考文献数

19

---

The natural evolution strategies (NESs) is a family of iterative methods for black-box function optimization. Instead of directly minimizing an objective function, NESs minimizes the expectation of the objective function value over an arbitrary parametric probability distribution. In each iteration, NESs updates parameters of the distribution by using an estimated natural gradient of the expectation of the objective function value. Exponential NES (xNES) is an effective method of NESs that uses the multivariate normal distribution as the probability distribution. Since the shape of a normal distribution can take the form of a rotated ellipse in the solution space, xNES shows relatively good performance for ill-conditioned and non-separable objective functions. However, we believe that xNES has two problems that cause performance degradation. The first problem is that the spread of normal distribution tends to shrink excessively even if the distribution does not cover a (local) optimal point. This will cause premature convergence. The second problem is that the learning rates for the parameters of distribution are not appropriate. The learning rates depend only on the dimension of objective function although they should be designed depending on all the factors that influence the precision of natural gradient estimation. Moreover, they are set to small values for preventing the premature convergence and these results in too slow convergence speed even if the distribution covers the optimal point. In order to remedy the problems of xNES, we propose a new method of NESs named the distance-weighted exponential natural evolution strategy (DX-NES). On several benchmark functions, we confirmed that DX-NES outperforms xNES and that DX-NES shows better performance than CMA-ES on the almost all functions.

著者

永田 裕一

出版者

人工知能学会

雑誌

人工知能学会論文誌 (ISSN:13460714)

巻号頁・発行日

vol.22, no.5, pp.542-552, 2007

被引用文献数

3

---

We propose an genetic algorithm (GA) that applies to the traveling salesman problem (TSP). The GA uses edge assembly crossover (EAX), which is known to be effective for solving the TSP. We first propose a fast implementation of a localized EAX where localized edge exchanges are used in the EAX procedure. We also propose a selection model with an effective combination of the localized EAX that can maintain population diversity at negligible computational costs. Edge entropy measure is used to evaluate population diversity. We demonstrate that the proposed GA is comparable to state-of-the-art heuristics for the TSP. Especially, the GA is superior to them on large instances more than 10,000 cities. For example, the GA found an optimal solution of brd14051 (14,051 cities instance) with a reasonable computational cost. The results are quite impressive because the GA does not use Lin-Kernighan local search (LKLS) even though almost all existing state-of-the-art heuristics for the TSP based on LKLS and its variants.