Tips & Tricks: Handling expensive evaluation functions in Evolutionary Computation

Evolutionary algorithms (EA) have become very popular for solving complex optimization / data based modeling problems as, generally, they are fairly robust, easy to use and able to produce high quality results.

A common problem in real-word applications is the fact that the evaluation/fitness function employed by this type of algorithms is quite expensive (time-wise or even financially) to evaluate. As such, when taking into consideration the restrictions imposed on the running time of the EA, only a limited amount of fitness evaluations can be performed and this usually has a huge impact on the quality of the obtained solutions.

The approaches that have been proposed by scientific literature to deal with this problem roughly fall within two main categories:

• surrogate approximation - construct a new (faster to evaluate) expression of the objective function based on previous input to output mappings obtained using the original (expensive) evaluation function.
• evolutionary approximation - reduce the number of expensive fitness evaluations performed during the run by trying to estimate the fitness of an individual without using the costly evaluation function by combining information from other similar individuals that have already been evaluated and, if available, information regarding parameter sensitivity.

Two of the most common methods for surrogate approximation are based on neural networks (NNs) or support vector machines (SVMs). The idea behind the approach is quite simple: when having a sufficient number of individual fitness evaluations (i.e. sampling data), try to train a NN or a SVM model that can approximate reasonably well the actual expensive fitness evaluation function. The quality of the approximation depends a lot on the complexity and roughness of the search space, on the amount of sampling data and of course on the choice of NN or SVM kernel. After the surrogate NN or SVM model has been trained we can use it to perform a lot of inexpensive but relatively accurate fitness evaluations during parts, or even during the entire run of the EA.

Evolutionary approximation is based on the fact that, for most search spaces, two individuals that share many common features also tend to have a similar fitness value. For example, if in an EA's individuals are coded by a real parameter vector containing 15 values and one individual has 14 values that match exactly the values of an individual that has been evaluate 3 generations before and the 15 value is only slightly different, we can approximate the fitness of the current individual with that of its ancestor. This is a very brute approximation, that can be extended and refined (i.e. using advanced similarity metrics, interpolation, variable correlation information, local mappings, etc) according to the concrete problem at hand.

Hybrid strategies are also worth mentioning. One idea could be to use the surrogate models especially in the middle stages of the EA run and then to switch back to the original fitness evaluation function at the the very end stages of the run, when precision is of the utmost importance.  

Tips&Tricks: A little bit on personal information security - Tor and TrueCrypt

In these most auspicious times for social networking, business cloud migration and setting trends on twitter about Justin Bieber, I'll try to draw a bit more attention towards two open-source, free, industry proven, high quality pieces of software that can help you add a little more privacy and security to your personal information (if for whatever conspiracy theory driven reason you would feel the need to).

Tor (anonymity network) is a system, composed of client software and a network of volunteer servers, dedicated to ensuring online anonymity by helping to hide information about users' location and other factors which may help to identify them. Tor is an open-source implementation of the onion routing concept. Simplified, a message is repeatedly encrypted (n times) by the sender and then sent over n (randomly chosen) onion nodes to the receiver; each onion node removes one layer of encryption and forwards the message to the next node until the final exit node in the chain removes the last layer of encryption and forwards the message to its intended receiver. An onion node only has information about the node where it received the message from and the node to which it should forward the peeled message to. At no point along the path (except the exit onion node) does a routing node on the path hold the original message, the sender and the receiver. The combinination between Tor and a TLS system (e.g. HTTPS - check out The HTTPS Everywhere Project) removes the exit node vulnerability and makes for a quite free and robust online anonymity tool. Tor is free to download and extremely easy to install and use. Tor is by no means fail safe but it does a very good job at trying to keep your online anonymity intact from the perspective of message route path tracking.

TrueCrypt is a free, state of the art, on-the-fly encryption (OTFE) software that is compatible with Windows (7/Vista/XP), Mac OS X and Linux. It supports the AES, Twofish and Serpent encryption algorithms as well as various combinations of cascaded algorithms. Most importantly, on most current hardware architectures, parallelization and pipelining allow the system to read and write from/to an encrypted drive as fast as if the drive was not encrypted. TrueCrypt allows for the creation within a file of a virtual encrypted disk that can be mounted and unmounted, the encryption of an entire partition or storage device and plausible deniability tools like hidden volume and hidden operating system. TrueCrypt is also free to download and fairly simple to install and use.

I hope you found these software recommendations as interesting/useful as I did and I also hope that, if needed, they'll prove useful and save you some inconvenience. Now, let's get back to work and help trend #TrustInTheCloud #TheCloudIsSafe, #TheCloudCannotFail and #TheCouldIsYourFriend :P:D.

P.S. Some recently discovered Tor-based eye-candy.

Tips&Tricks: iWork Numbers - difference in minutes between two dates

I can work with relative ease with Excel and OpenOffice Spreadsheet but the iWork Numbers application was totally new for me. I was working on a report in Numbers and I didn't know how to calculate the difference in minutes between two date fields and, I must say, that I didn't find the information I needed fast enough on the web.

To keep the long story short, after 2-3 minutes of trial and error, I came across the answer: the formula I was looking for was:

DUR2MINUTES(Field1-Field2)

Hope this saves someone a bit of time.

Tips&Tricks: Two useful websites

During work on my Master Thesis here in Austria I came across two very useful websites. 

The first one provides a very fast online plotting tool for 2D and 3D functions that allows the user to specify basic viewing options. The resulting images can be saved in various formats. Another very nice feature is the permalink option which basically allows users to share their plots with others.

The second website is called Googlefight. As the name suggests, the idea behind it is fairly simple: search for two given terms and see which one of them is more popular in the eyes of the internet's all-mighty (i.e. which term yields more search results in Google). I found it very useful when I was not sure which term is more widely used in a given context.

Tips&Tricks: Meet Wordle

For someone who's main field of interest is IT , I must shamefully admit that there are still very cool programs out there that, though eluded my attention :)), are well known by almost all of my friends. One such program is Wordle created by Jonathan Feinberg. Wordle is basically a toy for generating "word clouds" from given input text. In these clouds, greater prominence is given to the words that appear more frequently in the input text. What makes it unique is the fact that you can tweak your clouds with different fonts, layouts, and color schemes and save them as images for the whole wide word to see.
.

Wordle also has an option for genereting clouds from RSS feeds. Here is are two clouds obtained for two of my posts. Can you guess for which ones? :))