Language for genetic algorithm

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
WallyNate
Posts: 3
Joined: Thu Jan 20, 2011 3:05 pm UTC

Language for genetic algorithm

Postby WallyNate » Tue Feb 01, 2011 4:42 pm UTC

So a few months ago I decided to attempt an implementation for one of my favorite euro-style card games. I decided to use Java, since it's a language I know fairly well, and it has easy sockets. However, I found an online implementation that is fantastic, depleting my motivation to make another implementation.

But I've been thinking lately about building an effective AI for this game, and I was thinking about using a genetic algorithm to make an AI for it. So I'm looking for a language that can run simulation games quickly and efficiently over millions of iterations (i.e. not Java). What language would be good for this kind of stuff? Perl? Python? Ruby? My main programming experience has been with Java/C/C++, but I'm looking to expand my language library.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Language for genetic algorithm

Postby Yakk » Tue Feb 01, 2011 5:00 pm UTC

Various imperative languages are going to be not all that much different in performance to each other. A factor of 10 to 100 is the best you are going to do, reasonably, by changing languages.

And a factor of 10 to 100 is small compared to the time you are going to be spending writing the program and debugging it and adding features and the like.

Perl, Python and Ruby are all interpreted languages. They aren't going to be fundamentally faster than Java at execution time.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
b.i.o
Green is the loneliest number
Posts: 2519
Joined: Fri Jul 27, 2007 4:38 pm UTC
Location: Hong Kong

Re: Language for genetic algorithm

Postby b.i.o » Tue Feb 01, 2011 6:47 pm UTC

And a factor of 10 to 100 is small compared to the time you are going to be spending writing the program and debugging it and adding features and the like.

While this may be true in general, it's definitely not true if you're doing genetic algorithm stuff or other things that are extremely computationally intense. GAs are really, really slow. A factor of 10 difference might mean waiting 30 minutes instead of 5 hours for a run, and when you can't really evaluate minor changes to your algorithm without doing a run of it, the difference starts becoming significant very quickly.

Perl, Python and Ruby are all interpreted languages. They aren't going to be fundamentally faster than Java at execution time.

In fact, not only are they not going to be faster, they're going to be very much slower (probably by about a factor of 50-100, depending on what, exactly, you're doing). From experience, doing GAs in Ruby/Python is an idea you'll regret later.

Java's actually quite fast. It would not be at all a bad choice for a GA implementation. You're only likely to get faster by going to C/C++ or *maybe* Haskell/Ocaml. If you're looking for something different (but not *too* different) but roughly equivalently fast to Java, I recommend taking a look at Scala. It's runs on the JVM, is interoperable with Java (you can use Java code directly from Scala, not so much the other way around), and it's (in my opinion) a lot less terrible of a language than Java is.

User avatar
headprogrammingczar
Posts: 3072
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

Re: Language for genetic algorithm

Postby headprogrammingczar » Tue Feb 01, 2011 7:01 pm UTC

Haskell/OCaml would have the benefits of provable correctness. It wouldn't be fun to run your simulation for a week, just to have a segfault from some array code wreck your day.
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you

kmatzen
Posts: 214
Joined: Thu Nov 15, 2007 2:55 pm UTC
Location: Ithaca, NY

Re: Language for genetic algorithm

Postby kmatzen » Tue Feb 01, 2011 8:24 pm UTC

We were taught how to do it in Common Lisp, but that's fairly archaic, I guess. It's really easy to code, but I doubt the interpreters are very fast at all.

User avatar
b.i.o
Green is the loneliest number
Posts: 2519
Joined: Fri Jul 27, 2007 4:38 pm UTC
Location: Hong Kong

Re: Language for genetic algorithm

Postby b.i.o » Tue Feb 01, 2011 8:44 pm UTC

Common Lisp (at least the SBCL implementation) is actually quite fast for a dynamic language. Significantly faster than Ruby/Python, and maybe approaching competitive with Java. (Although again, 'speed' depends a lot on what you're doing.)

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Language for genetic algorithm

Postby Xanthir » Wed Feb 02, 2011 1:12 am UTC

When properly typed, and avoiding unnecessary consing, Common Lisp can be equivalent to C in a good implementation like SBCL.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Briareos
Posts: 1940
Joined: Thu Jul 12, 2007 12:40 pm UTC
Location: Town of the Big House

Re: Language for genetic algorithm

Postby Briareos » Wed Feb 02, 2011 1:16 am UTC

Is consing slow? I always think of it as like the most basic of lisp operations.
Sandry wrote:Bless you, Briareos.

Blriaraisghaasghoasufdpt.
Oregonaut wrote:Briareos is my new bestest friend.

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Language for genetic algorithm

Postby Xanthir » Wed Feb 02, 2011 1:19 am UTC

Consing requires memory allocation. Unnecessary consing triggers unnecessary GCing, which slows you down.

Yeah, Lisp is built on consing, but that doesn't necessarily mean it's the best idea when you're writing fast algorithms.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
WallyNate
Posts: 3
Joined: Thu Jan 20, 2011 3:05 pm UTC

Re: Language for genetic algorithm

Postby WallyNate » Wed Feb 02, 2011 2:34 am UTC

Thanks for the help guys! I knew C was faster that Java, but I have no idea why I thought Python was fast. I'll probably use C/C++, since it sounds like it'll be efficient.

...though using LISP is pretty tempting. I had a lot of fun with Scheme during college. Though I'm not sure how much tail recursion will help me in programming this card game :-P

User avatar
sircrayons
Posts: 86
Joined: Wed Mar 10, 2010 3:17 am UTC
Contact:

Re: Language for genetic algorithm

Postby sircrayons » Wed Feb 02, 2011 1:46 pm UTC

WallyNate wrote:Thanks for the help guys! I knew C was faster that Java, but I have no idea why I thought Python was fast. I'll probably use C/C++, since it sounds like it'll be efficient.


Python can be fast. It depends on many things, though, like the implementation and what you're asking it to do. Likewise, there are situations in which Java can be faster than, say, C++.

From experience, though, while writing a GA in Python can be fun, running one can be a painful commitment. C/C++ would most likely give you the performance you want. Another option is to write the non-GA bits in Python and everything else in C/C++.
"Ford, you're turning into a penguin. Stop it."


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 11 guests