Browsing by Author "Chen, Chao-Hong"

Now showing 1 - 6 of 6

Adaptive discretization for Probabilistic model building genetic algorithms
(2006)
Chen, Chao-Hong
;
Liu, Wei-Nan
;
Chen, Ying-Ping
;
資訊工程學系
;
Department of Computer Science
This paper proposes an adaptive discretization method, called Split-on-Demand (SoD), to enable the probabilistic model building genetic algorithm (PMBGA) to solve optimization problems in the continuous domain. The procedure, effect, and usage of SoD are described in detail. As an example, the integration of SoD and the extended compact genetic algorithm (ECGA), named real-coded ECGA (rECGA), is presented and numerically examined. The experimental results indicate that rECGA works well and SoD is effective. The behavior of SoD is analyzed and discussed, followed by the potential future work for SoD.
Automatically Proving Mathematical Theorems with Evolutionary Algorithms and Proof Assistants
(2016)
Yang, Li-An
;
Liu, Jui-Pin
;
Chen, Chao-Hong
;
Chen, Ying-ping
;
資訊工程學系
Mathematical theorems are human knowledge able to be accumulated in the form of symbolic representation, and proving theorems has been considered intelligent behavior. Based on the BHK interpretation and the Curry-Howard isomorphism, proof assistants, software capable of interacting with human for constructing formal proofs, have been developed in the past several decades. Since proofs can be considered and expressed as programs, proof assistants simplify and verify a proof by computationally evaluating the program corresponding to the proof. Thanks to the transformation from logic to computation, it is now possible to generate or search for formal proofs directly in the realm of computation. Evolutionary algorithms, known to be flexible and versatile, have been successfully applied to handle a variety of scientific and engineering problems in numerous disciplines for also several decades. Examining the feasibility of establishing the link between evolutionary algorithms, as the program generator, and proof assistants, as the proof verifier, in order to automatically find formal proofs to a given logic sentence is the primary goal of this study. In the article, we describe in detail our first, ad-hoc attempt to fully automatically prove theorems as well as the preliminary results. Ten simple theorems from various branches of mathematics were proven, and most of these theorems cannot be proven by using the tactic auto alone in Coq, the adopted proof assistant. The implication and potential influence of this study are discussed, and the developed source code with the obtained experimental results are released as open source.
Enabling the Extended Compact Genetic Algorithm for Real-Parameter Optimization by Using Adaptive Discretization
(2010-06-01)
Chen, Ying-ping
;
Chen, Chao-Hong
;
資訊工程學系
;
Department of Computer Science
An adaptive discretization method, called split-on-demand (SoD), enables estimation of distribution algorithms (EDAs) for discrete variables to solve continuous optimization problems. SoD randomly splits a continuous interval if the number of search points within the interval exceeds a threshold, which is decreased at every iteration. After the split operation, the nonempty intervals are assigned integer codes, and the search points are discretized accordingly. As an example of using SoD with EDAs, the integration of SoD and the extended compact genetic algorithm (ECGA) is presented and numerically examined. In this integration, we adopt a local search mechanism as an optional component of our back end optimization engine. As a result, the proposed framework can be considered as a memetic algorithm, and SoD can potentially be applied to other memetic algorithms. The numerical experiments consist of two parts: (1) a set of benchmark functions on which ECGA with SoD and ECGA with two well-known discretization methods: the fixed-height histogram (FHH) and the fixed-width histogram (FWH) are compared; (2) a real-world application, the economic dispatch problem, on which ECGA with SoD is compared to other methods. The experimental results indicate that SoD is a better discretization method to work with ECGA. Moreover, ECGA with SoD works quite well on the economic dispatch problem and delivers solutions better than the best known results obtained by other methods in existence.
Genetic Algorithms as Shrinkers in Property-Based Testing
(2019-01-01)
Lo, Fang-Yi
;
Chen, Chao-Hong
;
Chen, Ying-ping
;
交大名義發表
;
National Chiao Tung University
This paper proposes the use of genetic algorithms as shrinkers for shrinking the counterexamples generated by QuickChick, a property-based testing framework for Coq. The present study incorporates the flexibility and versatility of evolutionary algorithms into the realm of rigorous software development, in particular, making the results of property-based testing observable and comprehensible for human. The program code for merge sort is investigated as a showcase in the study. Due to the lack of similar proposals in the literature, random sample is used to compete with the proposal for comparison. The experimental results indicate that the proposed genetic algorithm outperforms random sample. Moreover, the minimal counterexamples, through which programmers are able to pinpoint the program mistakes with ease, can be successfully obtained by using genetic algorithms as shrinkers.
Quality Analysis of Discretization Methods for Estimation of Distribution Algorithms
(2014-05-01)
Chen, Chao-Hong
;
Chen, Ying-ping
;
資訊工程學系
;
Department of Computer Science
Estimation of distribution algorithms (EDAs). since they were introduced, have been successfully used to solve discrete optimization problems and hence proven to be an effective methodology for discrete optimization. To enhance the applicability of EDAs, researchers started to integrate EDAs with discretization methods such that the EDAs designed for discrete variables can be made capable of solving continuous optimization problems. In order to further our understandings of the collaboration between EDAs and discretization methods, in this paper, we propose a quality measure of discretization methods for EDAs. We then utilize the proposed quality measure to analyze three discretization methods: fixed-width histogram (FWH). fixed-height histogram (FHH), and greedy random split (GRS). Analytical measurements are obtained for FHH and FWH, and sampling measurements are conducted for FHH. FWH, and GRS. Furthermore, we integrate Bayesian optimization algorithm (BOA), a representative EDA, with the three discretization methods to conduct experiments and to observe the performance difference. A good agreement is reached between the discretization quality measurements and the numerical optimization results. The empirical results show that the proposed quality measure can be considered as an indicator of the suitability for a discretization method to work with EDAs.
Real-Coded ECGA for Economic Dispatch
(2007)
Chen, Chao-Hong
;
Chen, Ying-ping
;
資訊工程學系
;
Department of Computer Science
In this paper, we propose a new approach that consists of the extended compact genetic algorithm (ECGA) and split-on-demand (SoD), an adaptive discretization technique, to economic dispatch (ED) problems with nonsmooth cost functions. ECGA is designed for handling problems with decision variables of the discrete type, while the decision variables of ED problems are oftentimes real numbers. Thus, in order to employ ECGA to tackle ED problems, SoD is utilized for discretizing the continuous decision variables and works as the interface between ECGA and the ED problem. Furthermore, ED problems in practice are usually hard for traditional mathematical programming methodologies because of the equality and inequality constraints. Hence, in addition to integrating ECGA and SoD, in this study we devise a repair operator specifically for making the infeasible solutions to satisfy the equality constraint. To examine the performance and effectiveness, we apply the proposed framework to two different-sized ED problems with nonsmooth cost function considering the valve-point effects. The experimental results are compared to those obtained by various evolutionary algorithms and demonstrate that handling ED problems with the proposed framework is a promising research direction.