Genetic algorithms

Discussion of Common Lisp
Post Reply
Domus123
Posts: 12
Joined: Fri Oct 02, 2015 1:29 pm

Genetic algorithms

Post by Domus123 » Wed Apr 06, 2016 5:53 pm

Hey guys, i'm learning a bit of IA and i want to make a traveling salesman problem using GA .
So i have a doubt , i have some points pre-defined ex:

Code: Select all

(defvar a '(23 20))
(defvar b '(10 30))
(defvar c '(0 45))
(defvar d '(43 0))
How can i randomly create a list that contain all of it elements only one time ? I think some ways that wouldn't be very fast .

David Mullen
Posts: 78
Joined: Mon Dec 01, 2014 12:29 pm
Contact:

Re: Genetic algorithms

Post by David Mullen » Thu Apr 07, 2016 10:48 am

What are the elements of the list? I imagine a destructive shuffle would be fast enough—but that's assuming you already have a list for shuffling.

sylwester
Posts: 133
Joined: Mon Jul 11, 2011 2:53 pm

Re: Genetic algorithms

Post by sylwester » Sun Apr 10, 2016 4:25 pm

You can randomize it with sort:

Code: Select all

(defparameter *lst* (list a b c d)) ; list of the elements
(setf *lst* 
  (sort *lst* 
        (lambda (&rest lst) 
          (< 0.5 (random 1.0)))))
I'm the author of two useless languages that uses BF as target machine.
Currently I'm planning a Scheme compiler :p

Domus123
Posts: 12
Joined: Fri Oct 02, 2015 1:29 pm

Re: Genetic algorithms

Post by Domus123 » Mon Apr 11, 2016 5:26 pm

sylwester wrote:You can randomize it with sort:

Code: Select all

(defparameter *lst* (list a b c d)) ; list of the elements
(setf *lst* 
  (sort *lst* 
        (lambda (&rest lst) 
          (< 0.5 (random 1.0)))))

That code seems work,but how exactly that work?

David Mullen
Posts: 78
Joined: Mon Dec 01, 2014 12:29 pm
Contact:

Re: Genetic algorithms

Post by David Mullen » Wed Apr 13, 2016 1:07 pm

Domus123 wrote:
sylwester wrote:You can randomize it with sort:

Code: Select all

(defparameter *lst* (list a b c d)) ; list of the elements
(setf *lst* 
  (sort *lst* 
        (lambda (&rest lst) 
          (< 0.5 (random 1.0)))))
That code seems work,but how exactly that work?
It won't work with every sorting algorithm. With something like quicksort, you're partitioning the sequence recursively and rearranging each partition around some pivot element—with a random predicate, the pivot is irrelevant, of course. So it's like flipping a coin to decide whether to swap around a given element within the partition. Personally, I'd use a Fisher-Yates shuffle, which is like playing Bingo:

Code: Select all

(defun shuffle (list)
  (loop for tail on list
        for n downfrom (list-length list) above 1
        do (rotatef (car tail) (nth (random n) tail))
        finally (return list)))

pjstirling
Posts: 166
Joined: Sun Nov 28, 2010 4:21 pm

Re: Genetic algorithms

Post by pjstirling » Fri Apr 15, 2016 3:41 pm

I was actually surprised by it too, because the C++ sort is allowed to crash if your items comparison changes between calls. I wouldn't have even thought of doing it this way, but I checked the hyperspec and:
This is guaranteed even if the predicate does not really consistently represent a total order (in which case the elements will be scrambled in some unpredictable way, but no element will be lost)
Since that's exactly what is wanted here using RANDOM with SORT is fine.

Post Reply