The Ternary Operator

The ternary operator (the question mark and colon in the expression a ? b: c) is a tricky one.  It’s use is relatively uncommon, but it’s present in many programming languages, and sometimes it drastically simplifies a conditional assignment.  I bring it up because it was in the first version I saw of the GAA objective function, and it was doing something it shouldn’t have been.  Before I took up the GAA problem, some of the work involved allowing a 3 percent constraint violation.  This was still present in the objective function when I got my hands on it, although we no longer wanted to allow a 3 percent constraint violation.

Here’s what it looked like:


constr[0] = CV_TOTAL > 0.03 ? CV_TOTAL : 0.0;

What it does is assign CV_TOTAL to constr[0] only if CV_TOTAL is greater than 0.03, and otherwise it assigns 0 to constr[0].  It works this way because in general, the expression a ? b : c evaluates to b if a is true, and to c if a is false. So writing d = a ? b : c is a shorthand way of saying, “assign b to d if a is true, and assign c to d if a is false.”  And what it does in this case is allow 3% constraint violation.

My advice: there’s nothing wrong with using the ternary operator, but don’t be stingy with your comments.  Writing it like this could save you a lot of time:


constr[0] = CV_TOTAL > 0.03 ? CV_TOTAL : 0.0; // allow 3% constraint violation!

Of the  languages that I’ve used, the ternary operator shows up in this form in C, C++, Java, and Ruby.

Advertisements

Zotero introduction (video)

I made a short Screenr video describing how to install and use Zotero for citation management in Word. Specifically, the Zotero standalone program plus the Chrome plugin. (Sorry about the breathing sounds in the microphone … I’ll work on that next time.)

http://screenr.com/aZ5s

EDIT: As far as I can tell, WordPress only allows embedding from certain video sites which do not include Screenr. So I guess you have to just open the link. Sorry about that.

Edit by Rachel: Here is a second Screenr video I created about Zotero that talks about importing/exporting citations as well as using the PDF search capability in Zotero. I recommend watching this video using a full screen so you can read the text.

C++: Vectors vs. Arrays

In many of our programs we are using C-style arrays to store data. These are easy to write, but can be difficult to work with—they cannot be resized, they don’t know their own size, and most array operations require the use of pointers and memory management.

For many applications, you may want or need a data structure that is simpler to use. Check out the vector library in C++. The syntax for vectors may be new to you, but they make many operations a whole lot easier. A brief introduction to using the vector class is here.

Personally I like vectors because they make C++ operations more Matlab-esque, and they help prevent the memory management errors that are so common with C-style arrays. The downside, according to the C purists, is that vectors are slower than arrays. This can be true, depending on how you use them. But the vector class is really only an abstraction of the C-style array, so basic operations like storage and retrieval are still completed in constant time. The only time vectors slow down is when you append items to them, because behind the scenes, the vector is copying an entire array and adding a single element to it. This runs in O(N) time and can really slow things down if you do it every loop iteration. (Source: the tutorial above, and here).

So: vectors can make your life a lot easier, and they are the same speed as arrays for indexing operations. Just be careful to resize vectors as few times as necessary to preserve the efficiency of your program.

P.S. I’m sure there are dissenting opinions on the array/vector debate … please add your two cents.

C++ Training: Valgrind

Valgrind is a tool for “memory debugging” of programs. It allows you to find places where memory is not properly allocated, which are difficult to find using traditional debuggers. Valgrind should be one of the first steps that you take when testing a program — even a simple one! It is available on Penn State’s clusters, or available on Linux.

Here are some “fun” programming errors you should avoid that Valgrind will help catch:

Trying to write outside the bound

double *a;
length = 5;
a = new double[length]; //a is now an array of size 5
for (int i = 0; i < 6; i++)
{
   a[i] = i; //error at i=5
}

The program will let you write a value at a[5], even though the only legal places to write are a[0] through a[4]. This is a corruption, since a[5] refers to a place where memory could be used by another variable. Valgrind will yell at you for this, and rightly so. Also be careful when allocating 2d and 3d arrays, since it is easy to confuse rows and columns, which will cause you major headaches.

Memory Leaks Inside Functions

void fun()
{
   double *a;
   a = new double[5];
   return;
}

Although the variable a gets destroyed as you leave the function, the memory that you allocated here doesn’t get destroyed at all! This is dangerous, especially if you call fun() many times.

Conditional Jump Depends on Uninitialized Variables

Even if you allocate memory properly, you may unfortunately perform this horrible error:

int y; //uninitialized at first
int x = 6;
int *a;
a = new int[5];

if (x < 5)
{
   y = 2;
}

x[y] = 7; //error, since y is not initialized yet
delete a; //a is deallocated properly

Here we managed memory correctly, but we accessed y before it had a value assigned to it. The danger here is that y really has some garbage value (i.e., -58342671), so the program may “sometimes” call the line correctly, and sometimes it won’t. Valgrind to the rescue!

This tutorial explains how to start using it.

C++ Training: Makefiles

The following is a basic makefile that worked for me.  However, there’s a link at the bottom to a forum post that provides a better solution.

#The c++ compiler you'd like to use:
CC=g++

#the following is for normal use:
CFLAGS=-c -O3 -Wall
LDFLAGS=
#the following is for using gprof or valgrind (only comment out one at a time)
#CFLAGS=-g -pg -c -O3 -Wall
#LDFLAGS=-pg

#All your .cpp files go below. This simple example assumes they're all in the same directory:
SOURCES=calculations.cpp Dates.cpp Demands.cpp triangleSimulation.cpp

OBJECTS=$(SOURCES:.cpp=.o)

#Below you place your target name, what you want the program to be called.
EXECUTABLE=triangleSimulation

all: $(SOURCES) $(EXECUTABLE)

$(EXECUTABLE): $(OBJECTS)
    $(CC) $(LDFLAGS) $(OBJECTS) -o $@

.cpp.o:
    $(CC)  $(CFLAGS) $^ -o $@

clean:
    rm -rf *.o $(EXECUTABLE)

Forum post with advice on a simple makefile

MOEAs: Basic Concepts and Reading

(This post will be an introduction to the basic ideas behind MOEAs and will include references to relevant literature. Editors, please feel free to add citations as you see fit).

What is a MOEA?

Multi-objective evolutionary algorithms (MOEA) are used to optimize a set of decision variables with respect to a set of objectives. (The “multi-objective” distinction just means that more than one metric is being used to evaluate performance). In between the decision variables and objectives lies your model, which could be any application where performance needs to be optimized. For a detailed explanation of terminology related to decision variables and objectives, see Joe’s post. Evolutionary algorithms are considered heuristic methods because they do not solve problems deterministically, but rather explore the space of possible solutions and dynamically learn which decision variables lead to good performance. Perhaps the most comprehensive resource for learning about MOEAs is Evolutionary Algorithms for Solving Multi-Objective Problems by Coello Coello (ask around for hard or PDF copies). This can be a difficult read for those new to the subject, so you may want to read the rest of this post and peruse the suggested papers before diving in.

Why do we use them?

A number of different optimization strategies exist, including linear programming, response surface methods, and others. For some optimization problems, you can even find closed-form analytical solutions (think of finding function maxima in calculus). Compared to other strategies, evolutionary algorithms are often considered to be messy and inelegant; for example, in the Algorithm Design Manual, Steven Skeina refers to genetic algorithms as “voodoo”. EAs truly are the sledgehammer of optimization methods—but this is why we use them! In engineering, we frequently encounter all sorts of difficult problems, including: constrained non-convex (where you must travel through infeasible space to reach feasible space), multi-modal (many “false” local optima), and high-dimensional problems, in terms of both decision variables and output objectives. More elegant methods typically need to be reformulated on a per-problem basis, but modern MOEAs can handle these difficult problems without altering their implementation. We want a solver that is reliable and robust across problem types, which is why we turn to MOEAs. A good discussion of the motivation for multi-objective optimization from a management perspective is given in Brill et al. (1982) Modeling to Generate Alternatives (note that the specific algorithm they use is less important for our purposes).

How do they work? (Single-objective)

For simplicity, let’s start by looking at a basic single-objective EA. This description is mostly based on the early genetic algorithms, but please note that a wide variety of variations exist. An EA begins with a randomly selected population of solutions (i.e., it randomly selects parameter sets and evaluates them in your model). From here, the algorithm uses mathematical operators to guide its search. EAs generally employ three operators—crossover, mutation, and selection—although the specific form of these operators varies between algorithms. The crossover operator combines decision variables from two or more solutions to create new solutions. The mutation operator perturbs the decision variables of a single solution to look for improvement in its local vicinity. Finally, the selection operator determines which solutions are allowed to proceed to the next “generation” (the next cycle of running these operators) and which will be discarded. By performing this process over multiple generations, the algorithm is able to evolve the best-known solution (hence the analogies to biological evolution).

Some technical considerations

Every run of an EA is a battle between convergence toward the best solution (governed by the selection operator) and diversity of solutions (governed by the crossover and mutation operators). Ideally, we want fast convergence with maximum diversity, but a balance must be struck between the two—we can sacrifice some convergence speed to ensure that the algorithm does not converge prematurely to a local optimum.

We also must consider the mathematical properties of our problems and the difficulties these may pose for evolutionary search. The success of early EAs generally depends on whether the problem is decomposable (i.e., if the decision variables can be optimized individually). This is closely related to the concept of rotational invariance, which describes whether the decision variables interact with each other and thus need to be optimized together rather than individually. Finally, the success of EAs also depends on the causality of the problem: in a problem with strong causality, a small change in decision variables results in a small change in the objective function(s). We can expect EAs to perform better on problems that have both decomposability and strong causality. However, modern MOEAs utilize adaptive operator schemes to attempt to overcome these problems. A good discussion of testing the ability of EAs to overcome nasty problems (especially high dimensionality) is given by Deb et al. (2005) Scalable Test Problems.

Moving to multi-objective EAs

In a single-objective optimization, an EA will return only one point that is optimal with regard to the objective function. What if we want to incorporate multiple objectives? Our first thought might be to combine all of objectives together into one, using some kind of weighting scheme. However, this requires that we know ahead of time which objectives we care about most, and this is not always the case. Instead, we can incorporate all of our desired objective functions separately using the (crucial) principle of nondominance. In a set of solutions, a solution is said to be “dominated” if another solution exists which is better than it in all objectives. The solutions that are not dominated are said to be—you guessed it—”nondominated”. The set of all nondominated solutions in a given generation is referred to as the Pareto front or tradeoff surface (because objectives usually conflict with one another, resulting in multiple possible “best” solutions). So, rather than optimizing all of the objective functions themselves, modern MOEAs instead optimize the nondominance of solutions. The first algorithm to utilize this approach was Deb’s NSGA; Deb’s NSGAII (2002 paper) addressed many shortcomings of NSGA, and soon became extremely popular (to say the least). A thorough, broader discussion of multi-objective optimization is given by Fleming et al. 2005.

Where is the Pareto front?

A single run of a MOEA will provide a best-known approximation set of solutions, based on the principle of nondominance. But how do we know whether this is “right” or not? Many people have debated this question in more of a philosophical, mathematical sense. Practically speaking, we usually investigate this question using brute force. We don’t just run a MOEA one time—instead, we use many different random seeds, a high number of function evaluations, and sometimes even different algorithms. For example, our recent AWR study used 10 different algorithms with 50 random seeds each. Our approach to the question “is it right?” is just to take the results from all of these runs and find the final set of nondominated solutions, known as the reference set. This is the best-known set of solutions to the problem after performing as much evolution as computation allows. We can discuss whether a reference set is “right”, but from an engineering perspective, it is perhaps more important to discuss whether it provides a useful, diverse set of new solutions to the problem.

Improving efficiency: epsilon dominance

MOEAs rely on nondominated sorting to generate a set of optimal solutions. This is a computationally expensive operation, because an algorithm must compare every existing solution to every other solution. As a consequence, an algorithm may waste a lot of time sorting solutions that differ from each other by insignificant amounts. An important contribution to address this problem is the principle of epsilon dominance. Epsilon dominance asks the user to specify a desired precision for each objective value ahead of time in order to simplify the nondominated sorting operations. For example, you may only care about measuring cost to the nearest dollar, or for a big project, to the nearest thousand dollars. An algorithm will then only find the best solution within each “epsilon” of the objective space, rather than optimizing using full floating point precision. The theory behind epsilon dominance is discussed in Laumanns et al. 2002. Josh and Pat added epsilon dominance to NSGAII to create eNSGAII; a good description of the algorithm design and performance is given in their 2006 comparison paper. Finally, a clear example of the efficiency gains from epsilon dominance is given in Kollat and Reed (2007) Scaling Analysis.

Putting it all together: Visualizing alternatives

We perform all of this computation because, somewhere in the world, there are stakeholders who care about this problem. It would be somewhat unhelpful to approach these stakeholders with a 10-page ASCII printout of a reference set. If we want to increase the real-world impact of our heroic efforts, we need to provide stakeholders with visualizations of our best-known solutions. Fortunately for our group, Josh has created the Aerovis program to view solution sets in multiple dimensions. Aerovis allows us to explore our solution sets and identify regions of interest in the objective space, and allows stakeholders to easily see the full range of possible outcomes for their problem. Getting started with MOEAs involves a lot of in-depth technical effort, but it’s important not to lose sight of the big picture—ultimately, we want to present meaningful results to stakeholders in a visually appealing way. A company or government agency may not care what algorithm you used, or how many random seeds you ran, etc., but they certainly do care if you can provide them with a better solution than the status quo. Some great examples of visualizing practical results are given in the Kollat and Reed (2007) VIDEO paper and also Kasprzyk et al. 2011.

The reading listed here should get you started for now. I plan to write another post about more advanced topics, including MOEA diagnostics (why we need them, what they mean, etc.). If you want to get a head start on MOEA diagnostics, you can check out Dave and Pat’s recent paper in Evolutionary Computation. Thanks for reading and feel free to email jdh366 (at) cornell (dot) edu with questions.

Software to Install on Personal Computers

I’ve been working lately with some visiting students, people outside the research group, and new students within the group that need to install some software on a personal laptop to get started.  Here is a guide to what you need to install. (Last Updated January 20, 2012).

  • (Required, Available to ANGEL Group Members Only)  If you haven’t already done so, contact Josh Kollat to become part of the AeroVis user group on Penn State’s ANGEL course management system, http://cms.psu.edu/.  There, you can download AeroVis, which is the visualization software that we use.  Also grab a copy of the sample data files and documentation which are really helpful.
  • (Required, Available to Everyone) Cygwin is used to connect to the cluster and see visual programs such as Matlab that are running on the cluster.  It can be found at http://www.cygwin.com/.  Download setup.exe and save it in a place (such as your Documents folder) where you will remember where to find it, since you may need to run it again.  Double click on setup.exe to get started.  You can either select the “default” packages when it asks which packages to install, or go ahead and select “all” to install all packages.  Either way, you may have to go back and select additional packages in subsequent runs of setup.exe if everything doesn’t install right.  The main package we’ll be using is “X-Window”, but according to their website, you install X-Window by following the same process of installing the cygwin package.  This is probably the hardest of any of the software packages to install, and it takes a long time.  Let us know if you need any help, and you can leave a comment if you have any tips on how to make the install process easier.  Afterwards, change your windows environment variables to add ;C:\cygwin\bin to your windows path. Note: Ryan has some additional ideas about the best way to access remote computers. Stay tuned for his post on the subject, and he can edit this post too with more details.
  • (Required, Available to Everyone) You’ll need a text editor, such as Notepad++ or PSPad.  Try both and see which one you like better, they are both free.  While you can use notepad or wordpad to do a lot of the text editing, these programs are a lot more comfortable for working with data and programming.
  • (Required, Available to Everyone) Use WinSCP for file transfer to the cluster.Ryan’s suggestions will probably pertain to this advice too. I know Matt and Ryan use different software packages so I’d love their input here. See comments to this post for additional discussion about this.
  • (Required Only for Visiting Students who Need College of Engineering Wireless) A group member can contact Bob White to get access for you.  A Penn State student must download software at the college’s site and load it on the visitor’s laptop.
  • (Required for Most Students Publishing Papers and Writing Theses Internally in the Group) You’ll need a LaTeX system. LyX is an open source “document processor” that has compatability with LaTeX. Please add additional suggestions for LaTeX environments and editors, preferably ones with syntax highlighting and some graphical features (such as adding equations using symbols). We have a license for WinEdt, but it’s not free for personal use.
  • (Optional, Available to Everyone)  Open source tips:  When in a Penn State computer lab or at a computer in our office, you can use Adobe Photoshop and Illustrator for figure editing and Microsoft Office products.  If you want access to some nice programs on your personal computer, though, for free, try Inkscape (for vector images), GIMP (for raster images and pictures), and Open Office (an alternative to Microsoft) which are all freely available.
  • (Optional, Available to Penn State Students Only) Some good software is available at http://downloads.its.psu.edu/.  Secure Shell Client, under “File Transfer” at that site, is a file transfer/terminal program used to connect to the cluster.  Different people have varying preferences for file transfer and cluster stuff.  I personally recommend WinSCP and running terminal commands on Cygwin, so Secure Shell is not really required.

As far as software that costs money or for computers in the office, we would generally need Microsoft Office, Microsoft Visual Studio, Matlab, and the Adobe Suite.  Students shouldn’t have to worry about installing those programs on their personal computers.  If you get Cygwin working correctly, your cluster access will allow you to use Matlab, Mathematica, programming compilers, and other software, so even if you don’t have access to your own copy of Matlab, you can use it interactively on the cluster.

Let me know if you have any questions by emailing jrk301 at psu.edu.