Browsing by Author "Chen, Ying-ping"

Now showing 1 - 20 of 40

Analysis of particle interaction in particle swarm optimization
(2010-05-06)
Chen, Ying-ping
;
Jiang, Pei
;
資訊工程學系
;
Department of Computer Science
In this paper, we analyze the behavior of particle swarm optimization (PSO) on the facet of particle interaction. We firstly propose a statistical interpretation of particle swarm optimization in order to capture the stochastic behavior of the entire swarm. Based on the statistical interpretation, we investigate the effect of particle interaction by focusing on the social-only model and derive the upper and lower bounds of the expected particle norm. Accordingly, the lower and upper bounds of the expected progress rate on the sphere function are also obtained. Furthermore, the sufficient and necessary condition for the swarm to converge is derived to demonstrate the PSO convergence caused by the effect of particle interaction. (C) 2010 Elsevier B.V. All rights reserved.
Artistic Image Processing with Cellular Automata and Evolutionary Algorithms
(2015)
Tseng, Hsuan-wen
;
Chen, Ying-ping
;
資訊工程學系
;
Department of Computer Science
Scientists and artists have been dedicate themselves to combine science and art together for decades, especially in the realm of computer science and digital technology. Nowadays, there are commercial software packages providing artistic image effect filters and processors. These functionalities are usually designed for certain specific purposes, such as blur, sketch, and the like. In this study, we make our attempt to develop a mechanism which is able to generate many different kinds of artistic effects, many of which are probably difficult to describe. The proposed mechanism combines cellular automata and pixel painting to process a given image with the involvement of an evolutionary algorithm. Interesting and/or unexpected results are obtained via the use of the evolutionary algorithm on the objective functions presented in this paper.
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.
Cache Replacement Algorithms for YouTube
(2014-01-01)
Lee, Ming-Chang
;
Leu, Fang-Yie
;
Chen, Ying-ping
;
資訊工程學系
;
Department of Computer Science
In recent years, many social network systems like, YouTube, Facebook, Twitter, etc. have been a part of our everyday life. Among these systems, YouTube which plays video programs of different interesting themes for users has been one of the most attractive ones. Basically, when the space of Memcached in YouTube is full, the Least Recently Used algorithm (LRU for short) is employed to evict a least recently watched video. However, the LRU, due to its own property, may cause more miss counts of Memcached for YouTube, consequently increasing the network bandwidth and energy consumptions. To solve these problems, in this paper we proposed two cache replacement algorithms, the Pareto Least Recently Used algorithm (PLRU for short) and Pareto Least Frequently Used algorithm (PLFU for short), in which videos are classified into different popularity categories, and those videos in the top 10% and 20% of the top two popular categories of YouTube, based on Pareto principle, are then chosen to serve users\' requests without removing them from Memcached. The simulation results show that the PLFU algorithm can significantly reduce miss counts of Memcached compared with those when the LRU and Least Frequently Used algorithm (LFU for short) are employed, thus achieving great performance improvements for the top two popular categories of videos. Also, when a large space of Memcached is available, the miss counts of the PLRU are higher than those of the LRU. But when comparing them in a small available Memcached space, the miss counts of the LRU on the contrary is higher than those of the PLRU.
Characteristic Determination for Solid State Devices with Evolutionary Computation: A Case Study
(2007)
Hung, Ping-Chu
;
Chen, Ying-ping
;
Zan, Hsiao Wen
;
資訊工程學系
;
Department of Computer Science
In this paper, we develop a new optimization framework that consists of the extended compact genetic algorithm (ECGA) and split-on-demand (SoD) to tackle the characteristic determination problem for solid state devices. As most decision variables of characteristic determination problems are real numbers due to the modeling of physical phenomena, and ECGA is designed for handling discrete-type problems, a specific mechanism to transform the variable types of the two ends is in order. In the proposed framework, ECGA is used as an optimization engine, and SoD is adopted as the interface between the engine and the problem. Moreover, instead of one mathematical model with various parameters. characteristic determination is in fact a set of problems of which the mathematical formulations may be very different. Therefore, in this study, we employ the proposed framework oil three study cases to demonstrate that the technique proposed in the domain of evolutionary computation can provide not only the high quality optimization results but also the flexibility to handle problems of different formulations.
Connection Choice Codes
(2014-07-01)
Chen, Chih-Ming
;
Chen, Ying-ping
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
Luby Transform (LT) codes are the first practical implementation of digital fountain codes. In LT codes, encoding symbols are independently generated so as to realize the universal property which means that performance is independent of channel parameters. The universal property makes LT codes able to provide reliable delivery simultaneously via channels of different quality while it may also limit the flexibility of LT codes. In certain application scenarios, such as real-time multimedia transmission, most receivers have tolerable channels whose erasure rates are not fixed, and channels of high erasure rate are outside the design box. In this paper, Connection Choice (CC) codes are proposed to trade the universal property for better performance. The key to CC codes is replacement of random selection with tournament selection. Tournament selection can equalize the frequency of input symbols to join encoding and change the degree distribution of input symbols. Our study indicates that CC codes with appropriate degree distributions provide better performance than the best known LT code when channels of high erasure rate can be ignored. CC codes enable system designers to customize digital fountain codes by taking into account the distribution of the erasure rate and create a new possibility for setting trade-offs between performance and erasure rate.
Contrapuntal Composition and Autonomous Style Development of Organum Motets by using AntsOMG
(2019-06-28)
Chang, Chun-yien
;
Chen, Ying-ping
;
資訊工程學系
;
Department of Computer Science
Controlling the movement of crowds in computer graphics by using the mechanism of particle swarm optimization
(2009-06-01)
Chen, Ying-ping
;
Lin, Ying-yin
;
資訊工程學系
;
Department of Computer Science
This paper presents a uniform conceptual model to co-operate with particle swarm optimization (PSO) for controlling the movement of crowds in computer graphics. According to the PSO mechanism, each particle in the swarm adopts the information to automatically find a path from the initial position to the optimum. However, PSO aims to obtain the optimal solution instead of the searching path, while the purpose of this work concentrates on the control of the crowd movement, which is composed of the generated searching paths of particles. Hence, in order to generate seemingly natural, appropriate paths of people in a crowd, we propose a model to work with the computational facilities provided in PSO. Compared to related approaches previously presented in the literature, the proposed model is simple, uniform, and easy to implement. The results of the conducted simulations demonstrate that the coupling of PSO and the proposed technique can generate appropriate non-deterministic, non-colliding paths for the use in computer graphics for several different scenarios, including static and dynamic obstacles, moving targets, and multiple crowds. (C) 2009 Elsevier B. V. All rights reserved.
Crowd control with swarm intelligence
(2007)
Lin, Ying-yin
;
Chen, Ying-ping
;
資訊工程學系
;
Department of Computer Science
This paper presents a uniform conceptual model based on the particle swarm optimization (PSO) paradigm to simulate crowds in computer graphics. According to the mechanisms of PSO, each person (particle) in the crowd (swarm) can adopt the information to search a path from the initial position to the specified target (optimum) automatically. However, PSO aims to obtain the optimal solution, while the purpose of this study concentrates on the generated paths of particles. Hence, in order to generate appropriate paths of people in a crowd, we propose a method to employ the computational facilities provided in PSO. The proposed model is simple, uniform, and easy to implement. The results of simulations demonstrate that using PSO with the proposed technique can generate appropriate non-deterministic, non-colliding paths in several different scenarios, including static obstacles, moving targets, and multiple crowds.
Deriving Job Completion Reliability and Job Energy Consumption for a General MapReduce Infrastructure from Single-Job Perspective
(2013)
Lin, Jia-Chun
;
Leu, Fang-Yie
;
Lee, Ming-Chang
;
Chen, Ying-ping
;
資訊工程學系
MapReduce as a master-slave infrastructure consists of two master-side severs and a large number of slave-side working nodes. In this paper, we derive a job completion reliability (JCR for short) model from a single-job perspective for a general MapReduce infrastructure in which no redundancy scheme is adopted on the master side, and a cold-standby scheme is employed on the slave side. Without loss of generality, the JCR model is derived based on a Poisson distribution. In addition, we calculate the corresponding job energy consumption (JEC for short). Through the simulation and analytical results, MapReduce managers and service providers can comprehend how this infrastructure behaves and how to improve the infrastructure so as to achieve a more reliable and energy-efficient MapReduce environment.
Developing a Performance-analysis Model for a Star-Topology Data Grid from Multi-User Perspective
(2014)
Lee, Ming-Chang
;
Leu, Fang-Yie
;
Chen, Ying-ping
;
資訊工程學系
;
Department of Computer Science
Data grids often integrate many geographically dispersed storage and computational resources to provide users with an environment in which scientists and scientific researchers can execute their large-scale applications and store their data collected from other databases or produced by their experiments. To efficiently transfer a huge volume of data shared by users among the clusters or nodes in data grids, several co-allocation schemes have been proposed to shorten the data delivery. In this paper, we develop a performance-analysis model, named the Response Time Evaluation Model (RTEM for short), over a topology reduced from a tree to a star to evaluate data grid co-allocation schemes from multi-user perspective.
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.
Enhancing MOEA/D with Guided Mutation and Priority Update for Multi-objective Optimization
(2009)
Chen, Chih-Ming
;
Chen, Ying-ping
;
Zhang, Qingfu
;
資訊工程學系
;
Department of Computer Science
Multi-objective optimization is an essential and challenging topic in the domains of engineering and computation because real-world problems usually include several conflicting objectives. Current trends in the research of solving multi-objective problems (MOPs) require that the adopted optimization method provides an approximation of the Pareto set such that the user can understand the tradeoff between objectives and therefore make the final decision. Recently, an efficient framework, called MOEA/D, combining decomposition techniques in mathematics and optimization methods in evolutionary computation was proposed. MOEA/D decomposes a MOP to a set of single-objective problems (SOPs) with neighborhood relationship and approximates the Pareto set by solving these SOPs. In this paper, we attempt to enhance MOEA/D by proposing two mechanisms. To fully employ the information obtained from neighbors, we introduce a guided mutation operator to replace the differential evolution operator. Moreover, a update mechanism utilizing a priority queue is proposed for performance improvement when the SON obtained by decomposition are not uniformly distributed on the Pareto font Different combinations of these approaches are compared based on the test problem instances proposed for the CEC 2009 competition. The set of problem instances include unconstrained and constrained MOPs with variable linkages. Experimental results are presented in the paper, and observations and discussion are also provided.
Free lunches on the discrete Lipschitz class
(2011-04-08)
Jiang, Pei
;
Chen, Ying-ping
;
資訊工程學系
;
Department of Computer Science
The No-Free-Lunch theorem states that there does not exist a genuine general-purpose optimizer because all algorithms have the identical performance on average over all functions. However, such a result does not imply that search heuristics or optimization algorithms are futile if we are more cautious with the applicability of these methods and the search space. In this paper, within the No-Free-Lunch framework, we firstly introduce the discrete Lipschitz class by transferring the Lipschitz functions, i.e., functions with bounded slope, as a measure to fulfill the notion of continuity in discrete functions. We then investigate the properties of the discrete Lipschitz class, generalize an algorithm called subthreshold-seeker for optimization, and show that the generalized subthreshold-seeker outperforms random search on this class. Finally, we propose a tractable sampling-test scheme to empirically demonstrate the superiority of the generalized subthreshold-seeker under practical configurations. This study concludes that there exist algorithms outperforming random search on the discrete Lipschitz class in both theoretical and practical aspects and indicates that the effectiveness of search heuristics may not be universal but still general in some broad sense. (C) 2010 Elsevier B.V. All rights reserved.
Fusing creative operations into evolutionary computation for composition: From a composer's perspective
(2019-01-01)
Chang, Chun-yien
;
Chen, Ying-ping
;
資訊工程學系
;
Department of Computer Science
This paper presents a study on fusing creative operations into evolutionary computation for music composition, as an attempt to provide a collaborative creation environment between human and machine and to investigate into the mind process during music creation. A framework based on the paradigm of evolutionary computation is proposed to incorporate key mechanisms observed in the creation process and implemented to work on evolving abstract musical ideas and thoughts. The developed software framework is released as open source. The collaborative creation process, involving the framework, the composer, and the performer, is presented and discussed, and the results of this study also include a composed music work for unaccompanied cello, played by a renowned cellist.
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.
Impact of MapReduce Policies on Job Completion Reliability and Job Energy Consumption
(2015-05-01)
Lin, Jia-Chun
;
Leu, Fang-Yie
;
Chen, Ying-ping
;
資訊工程學系
;
Department of Computer Science
Recently, MapReduce has been widely employed by many companies/organizations to tackle data-intensive problems over a large-scale MapReduce cluster. To solve machine/node failure which is inevitable in a MapReduce cluster, MapReduce employs several policies, such as input-data replication and intermediate-data replication policies. To speed up job execution, MapReduce allows reduce tasks to early fetch their required intermediate data. However, the impact of these policy combinations on the job completion reliability (JCR for short) and job energy consumption (JEC for short) of a MapReduce cluster was not clear, where JCR is the reliability with which a MapReduce job can be completed by the cluster, whereas JEC is the energy consumed by the cluster to complete the job. Therefore, in this study, we analyze the JCR and JEC of a MapReduce cluster on four policy combinations (POCs for short) derived from two typical intermediate-data replication policies and two typical reduce-task assignment policies. The four POCs are further compared in extensive scenarios, which not only consider jobs at different scales with various parameters, but also give a MapReduce cluster two extreme parallel execution capabilities and diverse bandwidths. The analytical results enable MapReduce managers to comprehend how these POCs impact the JCR and JEC of a cluster and then select an appropriate POC based on the characteristics of their own MapReduce jobs and clusters.
Impact of MapReduce Task Re-execution Policy on Job Completion Reliability and Job Completion Time
(2014-01-01)
Lin, Jia-Chun
;
Leu, Fang-Yie
;
Chen, Ying-ping
;
Munawar, Waqaas
;
資訊工程學系
MapReduce has been a worldwide accepted framework for solving data-intensive applications. To prevent MapReduce jobs from being interrupted by node failures which occur frequently in a large-scale MapReduce cluster, current MapReduce implementations, e.g., Hadoop, employ a task re-execution policy (TR policy for short) for MapReduce jobs, i.e., when a map/reduce task of a job fails due to node failure, this policy reperforms the task on another node. However, the impact of the TR policy on job completion reliability and job completion time have not been studied from a theoretical viewpoint, especially when the job is given different characteristics, e.g., different input data sizes, different numbers of reduce tasks, and different intermediate data sizes. In this study, we derive the job completion reliability (JCR for short) of a MapReduce job based on Poisson distributions and analyze the expected job completion time (JCT for short) based on the universal generation function. We use nine settings of task re-execution factor (TR factor for short) to explore the impact of the TR policy on the JCR and JCT of jobs. The results show that the TR policy can effectively improve JCR without significantly prolonging JCT. But there is no single TR factor with which all jobs can achieve a high JCR.
Impacts of Task Re-Execution Policy on MapReduce Jobs
(2016-05)
Lin, Jia-Chun
;
Leu, Fang-Yie
;
Chen, Ying-ping
;
資訊工程學系
;
Department of Computer Science
MapReduce is a popular distributed programming framework for large-scale data processing. To prevent MapReduce jobs from being interrupted by node failures that occur frequently in a MapReduce cluster consisting of a set of commodity machines/nodes, the most well-known MapReduce implementation, i.e. Hadoop, adopts a task re-execution policy (TR policy). When a map/reduce task of a job crashes, the TR policy assigns another node to reperform the task. However, the impact of the TR policy on MapReduce jobs in terms of reliability, job turnaround time (JTT) and energy consumption are not clear, particularly when jobs have different features, e.g. different filtering percentages, different input-data sizes, and different numbers of reduce tasks. In this paper, we formally analyze the job completion reliability (JCR) of a job based on Poisson distributions, and then derive the expected JTT and job energy consumption (JEC) based on the universal generation function. Extensive analyses are further conducted to explore the impact of the TR policy on JCR, JTT and JEC of jobs with different features. The results show that employing the TR policy can dramatically improve JCR for a large MapReduce job. Moreover, if the JCR of a job is highly improved by the TR policy, the expected JTT and JEC will not be significantly prolonged and increased, respectively.
In the Name of Creativity: En Route to Inspiring Machines
(2021-09-14)
Chang, Chun-yien
;
Chen, Ying-ping
;
Department of Computer Science
;
資訊工程學系