Thiago Pradi

Computer Science, Health Informatics and Ruby.

Introduction to Metaheuristics

Hello Readers,

Today I’ll start my series of posts about genetic algorithms in Ruby.

Starting from the beginning, I’ll give an introduction about Artificial Intelligence and Metaheuristics.

But, to start, we need to know what is Artificial Intelligence. To help us, here is a little quote from John McCarthy about the subject:

Q. What is artificial intelligence?

A. It is the science and engineering of making intelligent machines, especially intelligent computer programs. It is related to the similar task of using computers to understand human intelligence, but AI does not have to confine itself to methods that are biologically observable.

To summarize, the focus of Artificial Intelligence is to make computer smarter and sometimes, take solutions inspired by biological behavior that exists in nature. For me, it’s one of the most interesting branches in computer science.

Related to the Intelligence is the capacity of solving problems. Some computacional problems are easily solved in polynomial time (like sorting a list), but some of them couldn’t be solved in polynomial time (like the Travelling Salesman Problem, for example).

In a attempt to build a better strategy to solve those problems in polynomial time, there is the field of Metaheuristics. This field consist basically in building strategies and algorithms to gradually improve an initial solution in order to achieve the best possible solution in a polinomial time.

Again, to help us understand more about Metaheuristics, here is a quote from Sean Luke:

What is a Metaheuristic?

A common but unfortunate name for any stochastic optimization algorithm intended to be the last resort before giving up and using random or brute-force search. Such algorithms are used for problems where you don’t know how to find a good solution, but if shown a candidate solution, you can give it a grade.

There are many different Metaheuristics that have been developed to solve different types of problems. To illustrate and give a better understanding of them, I have detailed a few in the next section.

Genetic algorithms:

Genetic Algorithms are a search heuristics that tries to copy and apply the same process that the nature uses for evolution into solving computer problems. This heuristic was developed by John Holland and his collegues in 1975, and is being used in a huge class of different problems.

Hill-climbing:

Hill-climbing is a type of local search, that aims to improve the current solution by looking at the neighbors to the current state, and takes the neighbor state with the best objective function value as the new current state. They are also called Greedy Algorithms, because they pick the best neighbor for the current state, without considering future steps.

Simulated annealing:

The simulated annealing algorithm is an metaheuristic for global optimization, inspired by the process of annealing in metal work. In the same way that metal cools its structure and become fixed in the nature, we set an initial temperature that decrease by every interaction, allowing the algorithm to accept worse solutions in the beginning (to explore a bigger space), and make it only accept better solution as the temperature goes down. The design of this algorithm make it perfect to solve the travelling salesman problem.

Ant colony optimization:

Initially proposed by Marco Dorigo in 1992 in his PhD thesis, Ant colony optimization is a metaheuristic based on the based on the behavior of ants seeking a path between their colony and a source of food. To resume this techinique, it solves problems that can be reduced to finding good paths through graphs.

Wrapping up

In this post, I tried to introduce the concepts of Artificial intelligence, metaheuristics, and described a few metaheuristics. All of those explanations about specific heuristics are shorter, because every they will be described more detailed in the next posts of this series. In my next post, I’ll start going deep into every Metaheuristic, giving a implementation in Ruby. The first one will be the Hill-Climbing.

Genetic Algorithms in Ruby

Hello Readers,

I’ll try to update this blog more often. A lot of things changed since the latest post, but I’ll try to make it short.

In this year, I joined a master program at UFPR, on the Imago Research Group. My work will be in the field of Computer Graphics and Health Informatics.

In order to finish my master’s, I need to get a few credits from classes. In the first semester, I started by doing a discipline on Artificial Intelligence, focused on Genetic Algorithms.

In order to study and understand better the algorithms, I developed a couple of them using Ruby. In the next couple of posts, I’ll walkthrough some algorithms and their ruby implementations. Stay tuned!

Database Tip 1: Why Validate_uniqueness_of Is Broken

This is a series of posts where I will be talking about some database tips for long time railers.

In the past, I’ve been working on many rails projects, including big ones, that relies only on Rails validations for checking all the Data Integrety before the model is saved in the Database.

For most of validations, this makes sense. but validate_uniqueness_of is terrible broken, and could lead you to a number of problems.

Imagine the following scenario:

You have your model user, which have a unique e-mail, like this:

1
2
3
4
class User < ActiveRecord::Base
  validate_presence_of :email
  validate_uniqueness_of :email
end

So, in your production environment, you have configured to use unicorn + ngnix, with 4 workers.

In your production environment, the user creating is wrapped into a transaction with more business logic. So, here is the problem:

  1. Worker 1 starts a user creation trasaction
  2. Worker 2 starts a user creation trasaction
  3. Worker 1 makes the query to see if this e-mail is already taken, which return false, because the user wasn’t persisted in the database yet.
  4. Worker 2 makes the query to see if this e-mail is already taken, which return false, because the user wasn’t persisted in the database yet.
  5. Worker 1 finish the transaction, inserting the user.
  6. Worker 2 finishes the trasaction, inserting a user with duplicated e-mail.

This could be easily solved using a unique index in the database, which raises a exception if a duplicated data is entered. The index could be created in a migration, using the following code:

1
add_index :users, :email, :unique => true

For more about unique indexes, check this article: Mysql Unique Indexes and this PostgreSQL Unique indexes

Protip: be nice to your users, and rescue from the exception when this occurs, putting a nice message, like the following code:

1
2
3
4
5
6
7
8
9
10
11
12
class UsersController < ActionController::Base

  def create
    User.transaction do
      # do user stuff
    end

  rescue ActiveRecord::StatementInvalid => e
    flash[:error] = "Something bad happens"
    redirect_to new_user_path
  end
end

New Blog

Hi Guys! This is my first post using my new blog engine. This blog is powered by Octopress

Some events that happenned this year gave me some extra motivation to start writing again, like getting my english skills on track again (it’s so worst now) and experiences in my new job / college.

Hope you guys like it!

Thanks,

Thiago