Browsing by Author "Chen, Ying-Ping"

Now showing 1 - 15 of 15

A Novel Evaluation Function for LT Codes Degree Distribution Optimization
(2014-01-01)
Tsai, Pei-Chuan
;
Chen, Chih-Ming
;
Chen, Ying-Ping
;
資訊工程學系
;
Department of Computer Science
Luby transform (LT) codes implements an important property called ratelessness, meaning a fixed code rate is unnecessary and LT codes can complete the transmission without channel status. The property is advantageous to transmit over certain environments such as broadcasting in heterogeneous networks or transmitting data over unknown channels. For this reason, improving LT codes is a crucial research issue in recent years. The performance of LT codes is decided by the code length and a probability mass function, called degree distribution, used in the encoding process. To improve the performance of LT codes, many studies proposed to optimize the degree distribution by using methods in evolutionary computation. One of the key steps in the evolutionary process is to evaluate decision variables for comparing the fitness of each individual. In the optimization of LT codes, it needs to repeatedly simulate the encoding/decoding process with a given distribution and evaluate the performance over a sufficient number of runs. Hence, a lot of computational resource is necessary for the optimization of LT codes. In this paper, we propose a heuristic function to evaluate the performance of LT codes. The evaluation function estimates the expected fraction of unsolved symbols with the specified code length, reception overhead, and degree distribution. Based on the proposed function, a huge number of evaluations is possible for searching for better degree distributions. We first verify the practicality of the proposed function and then employ it in a multi-objective evolutionary algorithm to investigate the tradeoff of LT codes between the computational cost and decoding performance.
A Practical Optimization Framework for the Degree Distribution in LT Codes
(2013-11-01)
Chen, Chih-Ming
;
Chen, Ying-Ping
;
Shen, Tzu-Ching
;
Zao, John K.
;
資訊工程學系
LT codes are the first practical rateless codes whose reception overhead totally depends on the degree distribution adopted. The capability of LT codes with a particular degree distribution named robust soliton has been theoretically analyzed; it asymptotically approaches the optimum when the message length approaches infinity. However, real applications making use of LT codes have finite number of input symbols. It is quite important to refine degree distributions because there are distributions whose performance can exceed that of the robust soliton distribution for short message length. In this work, a practical framework that employs evolutionary algorithms is proposed to search for better degree distributions. Our experiments empirically prove that the proposed framework is robust and can customize degree distributions for LT codes with different message length. The decoding error probabilities of the distributions found in the experiments compare well with those of robust soliton distributions. The significant improvement of LT codes with the optimized degree distributions is demonstrated in the paper.
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.
Analysis on the Collaboration Between Global Search and Local Search in Memetic Computation
(2011-10-01)
Lin, Jih-Yiing
;
Chen, Ying-Ping
;
資訊工程學系
;
Department of Computer Science
The synergy between exploration and exploitation has been a prominent issue in optimization. The rise of memetic algorithms, a category of optimization techniques which feature the explicit exploration-exploitation coordination, much accentuates this issue. While memetic algorithms have achieved remarkable success in a wide range of real-world applications, the key to successful exploration-exploitation synergies still remains obscure as conclusions drawn from empirical results or theoretical derivations are usually quite algorithm specific and/or problem dependent. This paper aims to provide a theoretical model that can depict the collaboration between global search and local search in memetic computation on a broad class of objective functions. In the proposed model, the interaction between global search and local search creates a set of local search zones, in which the global optimal points reside, within the search space. Based on such a concept, the quasi-basin class (QBC) which categorizes problems according to the distribution of their local search zones is adopted. The subthreshold seeker, taken as a representative archetype of memetic algorithms, is analyzed on various QBCs to develop a general model for memetic algorithms. As the proposed model not only well describes the expected time for a simple memetic algorithm to find the optimal point on different QBCs but also consists with the observations made in previous studies in the literature, the proposed model may reveal important insights to the design of memetic algorithms in general.
Analyzing job completion reliability and job energy consumption for a heterogeneous MapReduce cluster under different intermediate-data replication policies
(2015-05-01)
Lin, Jia-Chun
;
Leu, Fang-Yie
;
Chen, Ying-Ping
;
資訊工程學系
;
Department of Computer Science
Recently, MapReduce has been a popular distributed programming framework for solving data-intensive applications. However, a large-scale MapReduce cluster has inevitable machine/node failures and considerable energy consumption. To solve these problems, MapReduce has employed several policies for replicating input data, storing/replicating intermediate data, and re-executing failed tasks. In this study, we concentrate on two typical policies for storing/replicating intermediate data, and derive the job completion reliability (JCR for short) and job energy consumption (JEC for short) of a MapReduce cluster when the two policies are individually employed. The two policies are further analyzed and compared given various scenarios in which jobs with different input data sizes, numbers of reduce tasks, and other parameters are run in a MapReduce cluster with two extreme parallel execution capabilities. From the analytical results, MapReduce managers are able to comprehend how the two policies influence the JCR and JEC of a MapReduce cluster.
AntsOMG: A Framework Aiming to Automate Creativity and Intelligent Behavior with a Showcase on Cantus Firmus Composition and Style Development
(2020-08-01)
Chang, Chun-yien
;
Chen, Ying-Ping
;
人文社會學院
;
資訊工程學系
;
College of Humanities and Social Sciences
Creative behavior is one of the most fascinating areas in intelligence. The development of specific styles is the most characteristic feature of creative behavior. All important creators, such as Picasso and Beethoven, have their own distinctive styles that even non-professional art lovers can easily recognize. Hence, in the present work, attempting to achieve cantus firmus composition and style development as well as inspired by the behavior of natural ants and the mechanism of ant colony optimization (ACO), this paper firstly proposes a meta-framework, called ants on multiple graphs (AntsOMG), mainly for roughly modeling creation activities and then presents an implementation derived from AntsOMG for composing cantus firmi, one of the essential genres in music. Although the mechanism in ACO is adopted for simulating ant behavior, AntsOMG is not designed as an optimization framework. Implementations can be built upon AntsOMG in order to automate creation behavior and realize autonomous development on different subjects in various disciplines. In particular, an implementation for composing cantus firmi is shown in this paper as a demonstration. Ants walk on multiple graphs to form certain trails that are composed of the interaction among the graph topology, the cost on edges, and the concentration of pheromone. The resultant graphs with the distribution of pheromone can be interpreted as a representation of cantus firmus style developed autonomously. Our obtained results indicate that the proposal has an intriguing effect, because significantly different styles may be autonomously developed from an identical initial configuration in separate runs, and cantus firmi of a certain style can be created in batch simply by using the corresponding outcome. The contribution of this paper is twofold. First, the presented implementation is immediately applicable to the creation of cantus firmi and possibly other music genres with slight modifications. Second, AntsOMG, as a meta-framework, may be employed for other kinds of autonomous development with appropriate implementations.
Detecting General Problem Structures with Inductive Linkage Identification
(2010-01-01)
Huang, Yuan-Wei
;
Chen, Ying-Ping
;
資訊工程學系
;
Department of Computer Science
Genetic algorithms and the descendant methods have been deemed robust, effective, and practical for the past decades. In order to enhance the features and capabilities of genetic algorithms, tremendous effort has been invested within the research community. One of the major development trends to improve genetic algorithms is trying to extract and exploit the relationship among decision variables, such as estimation of distribution algorithms and perturbation-based methods. In this study, we make an attempt to enable a perturbation-based method, inductive linkage identification (ILI), to detect general problem structures, in which one decision variable can link to an arbitrary number of other variables. Experiments on circular problem structures composed of order-4 and order-5 trap functions are conducted. The results indicate that the proposed technique requires a population size growing logarithmically with the problem size as the original ILI does on non-overlapping building blocks as well as that the population requirement is insensitive to the problem structure consisting of similar substructures as long as the overall problem size is identical.
Evolutionary interactive music composition
(2006)
Fu, Tao-Yang
;
Wu, Tsu-Yu
;
Chen, Chin-Te
;
Wu, Kai-Chu
;
Chen, Ying-Ping
This paper proposes the CFE framework-Composition, Feedback, and Evolution-and presents an interactive music composition system. The system composes short, manageable pieces of music by interacting with users. The most important features of the system include creating customized music according to the user preference and providing the facilities specifically designed for producing large amounts of music. We present the structure as well as the implementation of the system and the auxiliary functionalities that enhance the system. We also introduce the auto-feedback test with which we verify and evaluate the interactive music composition system.
High-performance solution-processed amorphous ZrInZnO thin-film transistors
(2012-10-01)
Chung, Ya-Wei
;
Chen, Fang-Chung
;
Chen, Ying-Ping
;
Chen, Yu-Ze
;
Chueh, Yu-Lun
We have developed amorphous zirconium-indium-zinc-oxide (ZrInZnO) as the channel layer to fabricate thin film transistors through a solution process. The best ZrInZnO transistor exhibited a field effect mobility of 3.80 cm2/Vs, an onoff ratio of similar to 107, a threshold voltage of 0.44 V and a subthreshold swing of 0.42 V/dec. The function of the Zr element was investigated through electrical and thin-film characterization. We found that Zr atoms behaved as effective carrier suppressors and the presence of Zr elements inhibited the crystallization of the InZnO phase. ((c) 2012 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)
iECGA: Integer extended compact genetic algorithm
(2006-01-01)
Hung, Ping-Chu
;
Chen, Ying-Ping
;
資訊工程學系
;
Department of Computer Science
Extended compact genetic algorithm (ECCA) is an algorithm that can solve hard problems in the binary domain. ECCA is reliable and accurate because of the capability of detecting building blocks, but certain difficulties are encountered when we directly apply ECGA to problems in the integer domain. In this paper, we propose a new algorithm that extends ECGA, called integer extended compact genetic algorithm (iECCA). iECGA uses a modified probability model and inherits the capability of detecting building blocks from ECGA. iECGA is specifically designed for problems in the integer domain and can avoid the difficulties that ECGA encounters. With the experimental results, we show the performance comparisons between ECCA, iECGA, and a simple GA. The results indicate that iECGA has good performance on problems in the integer domain.
iECGA: Integer extended compact genetic algorithm
(2006-01-01)
Hung, Ping-Chu
;
Chen, Ying-Ping
;
資訊工程學系
;
Department of Computer Science
Extended compact genetic algorithm (ECCA) is an algorithm that can solve hard problems in the binary domain. ECCA is reliable and accurate because of the capability of detecting building blocks, but certain difficulties are encountered when we directly apply ECGA to problems in the integer domain. In this paper, we propose a new algorithm that extends ECGA, called integer extended compact genetic algorithm (iECCA). iECGA uses a modified probability model and inherits the capability of detecting building blocks from ECGA. iECGA is specifically designed for problems in the integer domain and can avoid the difficulties that ECGA encounters. With the experimental results, we show the performance comparisons between ECCA, iECGA, and a simple GA. The results indicate that iECGA has good performance on problems in the integer domain.
Linkage identification by perturbation and decision tree induction
(2007)
Chuang, Chung-Yao
;
Chen, Ying-Ping
;
資訊工程學系
;
Department of Computer Science
The purpose of linkage identification in genetic and evolutionary algorithms is to detect the strongly related variables of the fitness function. If such linkage information can be acquired, the crossover or recombination operator can accordingly mix the discovered sub-solutions effectively without disrupting them. In this paper, we propose a new linkage identification technique, called inductive linkage identification (ILI), employing perturbation with decision tree induction. With the proposed scheme, the linkage information can be obtained by first constructing an ID3 decision tree to learn the mapping from the population of solutions to their corresponding fitness differences caused by perturbations and then inspecting the constructed decision tree for variables exhibiting strong interdependencies with one another. The numerical results show that the proposed technique can accomplish the identical linkage identification task with a lower number of function evaluations compared to similar methods proposed in the literature. Moreover, the proposed technique is also shown being able to handle both uniformly scaled and exponentially scaled problems.
PAReS: A Proactive and Adaptive Redundant System for MapReduce
(2015-09-01)
Lin, Jia-Chun
;
Leu, Fang-Yie
;
Chen, Ying-Ping
;
資訊工程學系
;
Department of Computer Science
Recently, MapReduce has been a key and popular technology for tackling data-intensive applications. But its two master servers in current MapReduce implementations have a single-point-of-failure problem, which may interrupt MapReduce operations and filesystem services. In this paper, we propose a hybrid takeover scheme, called PAReS (Proactive and Adaptive Redundant System). To further improve the master servers\' service qualities, PAReS also employs three service-quality improvement mechanisms, including a proactive synchronization and replication method, a mutual monitoring algorithm, and an adaptive warm-up mechanism. The extensive experiments show that PAReS enhances service quality at acceptable energy consumption level and synchronization cost as compared with four state-of-the-art schemes.
Particle swarm optimization with recombination and dynamic linkage discovery
(2007-12-01)
Chen, Ying-Ping
;
Peng, Wen-Chih
;
Jian, Ming-Chung
;
資訊工程學系
;
Department of Computer Science
In this paper, we try to improve the performance of the particle swarm optimizer by incorporating the linkage concept, which is an essential mechanism in genetic algorithms, and design a new linkage identification technique called dynamic linkage discovery to address the linkage problem in real-parameter optimization problems. Dynamic linkage discovery is a costless and effective linkage recognition technique that adapts the linkage configuration by employing only the selection operator without extra judging criteria irrelevant to the objective function. Moreover, a recombination operator that utilizes the discovered linkage configuration to promote the cooperation of particle swarm optimizer and dynamic linkage discovery is accordingly developed. By integrating the particle swarm optimizer, dynamic linkage discovery, and recombination operator, we propose a new hybridization of optimization methodologies called particle swarm optimization with recombination and dynamic linkage discovery (PSO-RDL). In order to study the capability of PSO-RDL, numerical experiments were conducted on a set of benchmark functions as well as on an important real-world application. The benchmark functions used in this paper were proposed in the 2005 Institute of Electrical and Electronics Engineers Congress on Evolutionary Computation. The experimental results on the benchmark functions indicate that PSO-RDL can provide a level of performance comparable to that given by other advanced optimization techniques. In addition to the benchmark, PSO-RDL was also used to solve the economic dispatch (ED) problem for power systems, which is a real-world problem and highly constrained. The results indicate that PSO-RDL can successfully solve the ED problem for the three-unit power system and obtain the currently known best solution for the 40-unit system.
XCS with Bit Masks
(2010-01-01)
Lin, Jia-Huei
;
Chen, Ying-Ping
;
資訊工程學系
;
Department of Computer Science
In this paper, a modified XCS is proposed to reduce the numbers of learned rules. XCS is a type of learning classifier systems and has been proven able to find accurate, maximal generalizations. However, XCS usually produces too many rules such that the readability of the classification model is greatly reduced. As a result, XCS users may not be able to obtain the desired knowledge or useful information from the learned rule set. In our attempt to handle this problem, a new mechanism, called bit masks, is devised in order to reduce the number of classification rules and therefore to improve the readability of the generated model. A series of n-bit multiplexer experiments, including 6-bit, 11-bit, and 20-bit multiplexers, to examine the performance of the proposed framework. For the problem composed of integertyped variables, two synthetic oblique datasets, Random-Data2 and Random-Data9, are adopted to compare the performance of XCS and that of the proposed method. According to the experimental results, XCS with bit masks can perform similarly as XCS on n-bit multiplexers and generates significantly fewer rules on integer-typed problems.