Open Access. Powered by Scholars. Published by Universities.®

Physical Sciences and Mathematics Commons™

Open Access. Powered by Scholars. Published by Universities.®

Computer Sciences

Ole J Mengshoel

Evolutionary Computation

Articles 1 - 9 of 9

Full-Text Articles in Physical Sciences and Mathematics

Darwin: A Ground Truth Agnostic Captcha Generator Using Evolutionary Algorithm, Eric Y. Chen, Lin-Shung Huang, Ole J. Mengshoel, Jason D. Lohn Jun 2014

Darwin: A Ground Truth Agnostic Captcha Generator Using Evolutionary Algorithm, Eric Y. Chen, Lin-Shung Huang, Ole J. Mengshoel, Jason D. Lohn

Ole J Mengshoel

We designed and implemented Darwin, the first CAPTCHA generator using evolutionary algorithm. We evaluated the effectiveness of our proposed CAPTCHAs with MTurk users (non-attackers) and Antigate workers (attackers). Due to our ground-truth agnostic fitness function, we are able to discover a new category of CAPTCHAs in which attackers answer correctly but non-attackers answer incorrectly.

Go to article

Feedback Control For Multi-Modal Optimization Using Genetic Algorithms, Jun Shi, Ole J. Mengshoel, Dipan K. Pal Jun 2014

Feedback Control For Multi-Modal Optimization Using Genetic Algorithms, Jun Shi, Ole J. Mengshoel, Dipan K. Pal

Ole J Mengshoel

Many optimization problems are multi-modal. In certain cases, we are interested in finding multiple locally optimal solutions rather than just a single optimum as is computed by traditional genetic algorithms (GAs). Several niching techniques have been developed that seek to find multiple such local optima. These techniques, which include sharing and crowding, are clearly powerful and useful. But they do not explicitly let the user control the number of local optima being computed, which we believe to be an important capability.
In this paper, we develop a method that provides, as an input parameter to niching, the desired number of …

Go to article

Adaptive Generalized Crowding For Genetic Algorithms, Ole J. Mengshoel, Severinio Galan, Antonio De Dios Dec 2013

Adaptive Generalized Crowding For Genetic Algorithms, Ole J. Mengshoel, Severinio Galan, Antonio De Dios

Ole J Mengshoel

The genetic algorithm technique known as crowding preserves population diversity by pairing each offspring with a similar individual in the current population (pairing phase) and deciding which of the two will survive (replacement phase). The replacement phase of crowding is usually carried out through deterministic or probabilistic crowding, which have the limitations that they apply the same selective pressure regardless of the problem being solved and the stage of genetic algorithm search. The recently developed generalized crowding approach introduces a scaling factor in the replacement phase, thus generalizing and potentially overcoming the limitations of both deterministic and probabilistic crowding. A …

Go to article

A Novel Mating Approach For Genetic Algorithms, Severino Galan, Ole J. Mengshoel, Rafael Pinter Dec 2012

A Novel Mating Approach For Genetic Algorithms, Severino Galan, Ole J. Mengshoel, Rafael Pinter

Ole J Mengshoel

Genetic algorithms typically use crossover, which relies on mating a set of selected parents. As part of crossover, random mating is often carried out. A novel approach to parent mating is presented in this work. Our novel approach can be applied in combination with a traditional similarity-based criterion to measure distance between individuals or with a fitness-based criterion. We introduce a parameter called mating index that allows different mating strategies to be developed within a uniform framework: from an exploitative strategy called BEST-FIRST to an explorative one called BEST-LAST. SELF-ADAPTIVE mating is defined in the context of the novel algorithm …

Go to article

Age-Layered Expectation Maximization For Parameter Learning In Bayesian Networks, Avneesh Saluja, Priya Sundararajan, Ole J. Mengshoel Apr 2012

Age-Layered Expectation Maximization For Parameter Learning In Bayesian Networks, Avneesh Saluja, Priya Sundararajan, Ole J. Mengshoel

Ole J Mengshoel

The expectation maximization (EM) algorithm is a popular algorithm for parameter estimation in models with hidden variables. However, the algorithm has several non-trivial limitations, a significant one being variation in eventual solutions found, due to convergence to local optima. Several techniques have been proposed to allay this problem, for example initializing EM from multiple random starting points and selecting the highest likelihood out of all runs. In this work, we a) show that this method can be very expensive computationally for difficult Bayesian networks, and b) in response we propose an age-layered EM approach (ALEM) that efficiently discards less promising …

Go to article

Generalized Crowding For Genetic Algorithms, Ole J. Mengshoel, Severino F. Galan Jun 2010

Generalized Crowding For Genetic Algorithms, Ole J. Mengshoel, Severino F. Galan

Ole J Mengshoel

Crowding is a technique used in genetic algorithms to preserve diversity in the population and to prevent premature convergence to local optima. It consists of pairing each offspring with a similar individual in the current population (pairing phase) and deciding which of the two will remain in the population (replacement phase). The present work focuses on the replacement phase of crowding, which usually has been carried out by one of the following three approaches: Deterministic, Probabilistic, and Simulated Annealing. These approaches present some limitations regarding the way replacement is conducted. On the one hand, the first two apply the same …

Go to article

Constraint Handling Using Tournament Selection: Abductive Inference In Partly Deterministic Bayesian Network, Severino F. Galan, Ole J. Mengshoel Dec 2008

Constraint Handling Using Tournament Selection: Abductive Inference In Partly Deterministic Bayesian Network, Severino F. Galan, Ole J. Mengshoel

Ole J Mengshoel

Constraints occur in many application areas of interest to evolutionary computation. The area considered here is Bayesian networks (BNs), which is a probability-based method for representing and reasoning with uncertain knowledge. This work deals with constraints in BNs and investigates how tournament selection can be adapted to better process such constraints in the context of abductive inference. Abductive inference in BNs consists of finding the most probable explanation given some evidence. Since exact abductive inference is NP-hard, several approximate approaches to this inference task have been developed. One of them applies evolutionary techniques in order to find optimal or close-to-optimal …

Go to article

The Crowding Approach To Niching In Genetic Algorithms, Ole J. Mengshoel, David E. Goldberg Dec 2007

The Crowding Approach To Niching In Genetic Algorithms, Ole J. Mengshoel, David E. Goldberg

Ole J Mengshoel

A wide range of niching techniques have been investigated in evolutionary and genetic algorithms. In this article, we focus on niching using crowding techniques in the context of what we call local tournament algorithms. In addition to deterministic and probabilistic crowding, the family of local tournament algorithms includes the Metropolis algorithm, simulated annealing, restricted tournament selection, and parallel recombinative simulated annealing. We describe an algorithmic and analytical framework which is applicable to a wide range of crowding algorithms. As an example of utilizing this framework, we present and analyze the probabilistic crowding niching algorithm. Like the closely related deterministic crowding …

Go to article

Probabilistic Crowding: Deterministic Crowding With Probabilistic Replacement, Ole J. Mengshoel, David E. Goldberg Jun 1999

Probabilistic Crowding: Deterministic Crowding With Probabilistic Replacement, Ole J. Mengshoel, David E. Goldberg

Ole J Mengshoel

This paper presents a novel niching algorithm, probabilistic crowding. Like its predecessor deterministic crowding, probabilistic crowding is fast, simple, and requires no parameters beyond that of the classical GA. In probabilistic crowding, subpopulations are maintained reliably, and we analyze and predict how this maintenance takes place.

This paper also identifies probabilistic crowding as a member of a family of algorithms, which we call integrated tournament algorithms. Integrated tournament algorithms also include deterministic crowding, restricted tournament selection, elitist recombination, parallel recombinative simulated annealing, the Metropolis algorithm, and simulated annealing.

Go to article