non_domination_sort_mod.html ( File view )

  • By moeah 2014-04-18
  • View(s):30
  • Download(s):1
  • Point(s): 1
			<html xmlns:mwsh="">
      <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
This HTML is auto-generated from an M-file.
To make changes, update the M-file and republish this document.
      <meta name="generator" content="MATLAB 7.0">
      <meta name="date" content="2006-03-16">
      <meta name="m-file" content="non_domination_sort_mod"><style>
body {

  background-color: white;

h1 {

  color: #990000; 
  font-size: x-large;

h2 {

  color: #990000;
  font-size: medium;

p.footer {

  text-align: right;
  font-size: xx-small;
  font-weight: lighter;
  font-style: italic;
  color: gray;


pre.codeinput {

  margin-left: 30px;


span.keyword {
color: #0000FF
span.comment {
color: #228B22
span.string {
color: #A020F0
span.untermstring {
color: #B20000
span.syscmd {
color: #B28C00

pre.showbuttons {

  margin-left: 30px;
  border: solid black 2px;
  padding: 4px;
  background: #EBEFF3;


pre.codeoutput {

  color: gray;
  font-style: italic;

pre.error {

  color: red;


/* Make the text shrink to fit narrow windows, but not stretch too far in 
wide windows.  On Gecko-based browsers, the shrink-to-fit doesn't work. */ 
p,h1,h2,div {

  /* for MATLAB's browser */
  width: 600px;
  /* for Mozilla, but the "width" tag overrides it anyway */
  max-width: 600px;
  /* for IE */
  width:expression(document.body.clientWidth > 620 ? "600px": "auto" );


            <li><a href="#1">function f = non_domination_sort_mod(x, M, V)</a></li>
            <li><a href="#2">Non-Dominated sort.</a></li>
            <li><a href="#3">Crowding distance</a></li>
            <li><a href="#4">References</a></li>
      <h2>function f = non_domination_sort_mod(x, M, V)<a name="1"></a></h2>
      <p>This function sort the current popultion based on non-domination. All the individuals in the first front are given a rank
         of 1, the second front individuals are assigned rank 2 and so on. After assigning the rank the crowding in each front is calculated.
      </p><pre class="codeinput">[N, m] = size(x);
clear <span class="string">m</span>

<span class="comment">% Initialize the front number to 1.</span>
front = 1;

<span class="comment">% There is nothing to this assignment, used only to manipulate easily in</span>
<span class="comment">% MATLAB.</span>
F(front).f = [];
individual = [];
</pre><h2>Non-Dominated sort.<a name="2"></a></h2>
      <p>The initialized population is sorted based on non-domination. The fast sort algorithm [1] is described as below for each</p><pre class="codeinput"><span class="comment">% &#149; for each individual p in main population P do the following</span>
<span class="comment">%   &#150; Initialize Sp = []. This set would contain all the individuals that is</span>
<span class="comment">%     being dominated by p.</span>
<span class="comment">%   &#150; Initialize np = 0. This would be the number of individuals that domi-</span>
<span class="comment">%     nate p.</span>
<span class="comment">%   &#150; for each individual q in P</span>
<span class="comment">%       * if p dominated q then</span>
<span class="comment">%           &middot; add q to the set Sp i.e. Sp = Sp ? {
<span class="comment">%       * else if q dominates p then</span>
<span class="comment">%           &middot; increment the domination counter for p i.e. np = np + 1</span>
<span class="comment">%   &#150; if np = 0 i.e. no individuals dominate p then p belongs to the first</span>
<span class="comment">%     front; Set rank of individual p to one i.e prank = 1. Update the first</span>
<span class="comment">%     front set by adding p to front one i.e F1 = F1 ? {
<span class="comment">% &#149; This is carried out for all the individuals in main population P.</span>
<span class="comment">% &#149; Initialize the front counter to one. i = 1</span>
<span class="comment">% &#149; following is carried out while the ith front is nonempty i.e. Fi != []</span>
<span class="comment">%   &#150; Q = []. The set for storing the individuals for (i + 1)th front.</span>
<span class="comment">%   &#150; for each individual p in front Fi</span>
<span class="comment">%       * for each individual q in Sp (Sp is the set of individuals</span>
<span class="comment">%         dominated by p)</span>
<span class="comment">%           &middot; nq = nq?1, decrement the domination count for individual q.</span>
<span class="comment">%           &middot; if nq = 0 then none of the individuals in the subsequent</span>
<span class="comment">%             fronts would dominate q. Hence set qrank = i + 1. Update</span>
<span class="comment">%             the set Q with individual q i.e. Q = Q ? q.</span>
<span class="comment">%   &#150; Increment the front counter by one.</span>
<span class="comment">%   &#150; Now the set Q is the next front and hence Fi = Q.</span>
<span class="comment">%</span>
<span class="comment">% This algorithm is better than the original NSGA ([2]) since it utilize</span>
<span class="comment">% the informatoion about the set that an individual dominate (Sp) and</span>
<span class="comment">% number of individuals that dominate the individual (np).</span>

<span class="comment">%</span>
<span class="keyword">for</span> i = 1 : N
    <span class="comment">% Number of individuals that dominate this individual</span>
    individual(i).n = 0;
    <span class="comment">% Individuals which this individual dominate</span>
    individual(i).p = [];
    <span class="keyword">for</span> j = 1 : N
        dom_less = 0;
        dom_equal = 0;
        dom_more = 0;
        <span class="keyword">for</span> k = 1 : M
            <span class="keyword">if</span> (x(i,V + k) &lt; x(j,V + k))
                dom_less = dom_less + 1;
            <span class="keyword">elseif</span> (x(i,V + k) == x(j,V + k))
                dom_equal = dom_equal + 1;
            <span class="keyword">else</span>
                dom_more = dom_more + 1;
            <span class="keyword">end</span>
        <span class="keyword">end</span>
        <span class="keyword">if</span> dom_less == 0 &amp;&amp; dom_equal ~= M
            individual(i).n = individual(i).n + 1;
        <span class="keyword">elseif</span> dom_more == 0 &amp;&amp; dom_equal ~= M
            individual(i).p = [individual(i).p j];
        <span class="keyword">end</span>
    <span class="keyword">end</span>
    <span class="keyword">if</span> individual(i).n == 0
        x(i,M + V + 1) = 1;
        F(front).f = [F(front).f i];
    <span class="keyword">end</span>
<span class="keyword">end</span>
<span class="comment">% Find the subsequent fronts</span>
<span class="keyword">while</span> ~isempty(F(front).f)
   Q = [];
   <span class="keyword">for</span> i = 1 : length(F(front).f)
       <span class="keyword">if</span> ~isempty(individual(F(front).f(i)).p)
        	<span class="keyword">for</span> j = 1 : length(individual(F(front).f(i)).p)
            	individual(individual(F(front).f(i)).p(j)).n = <span class="keyword">...</span>
                	individual(individual(F(front).f(i)).p(j)).n - 1;
        	   	<span class="keyword">if</span> individual(individual(F(front).f(i)).p(j)).n == 0
               		x(individual(F(front).f(i)).p(j),M + V + 1) = <span class="keyword">...</span>
                        front + 1;
                    Q = [Q individual(F(front).f(i)).p(j)];
                <span class="keyword">end</span>
            <span class="keyword">end</span>
       <span class="keyword">end</span>
   <span class="keyword">end</span>
   front =  front + 1;
   F(front).f = Q;
<span class="keyword">end</span>

[temp,index_of_fronts] = sort(x(:,M + V + 1));
<span class="keyword">for</span> i = 1 : length(index_of_fronts)
    sorted_based_on_front(i,:) = x(index_of_fronts(i),:);
<span class="keyword">end</span>
current_index = 0;
</pre><h2>Crowding distance<a name="3"></a></h2><pre class="codeinput"><span class="comment">%The crowing distance is calculated as below</span>
<span class="comment">% &#149; For each front Fi, n is the number of individuals.</span>
<span class="comment">%   &#150; initialize the distance to be zero for all the individuals i.e. Fi(dj ) = 0,</span>
<span class="comment">%     where j corresponds to the jth individual in front Fi.</span>
<span class="comment">%   &#150; for each objective function m</span>
<span class="comment">%       * Sort the individuals in front Fi based on objective m i.e. I =</span>
<span class="comment">%         sort(Fi,m).</span>
<span class="comment">%       * Assign infinite distance to boundary values for each individual</span>
<span class="comment">%         in Fi i.e. I(d1) = ? and I(dn) = ?</span>
<span class="comment">%       * for k = 2 to (n ? 1)</span>
<span class="comment">%           &middot; I(dk) = I(dk) + (I(k + 1).m ? I(k ? 1).m)/fmax(m) - fmin(m)</span>
<span class="comment">%           &middot; I(k).m is the value of the mth objective function of the kth</span>
<span class="comment">%             individual in I</span>

<span class="comment">% Find the crowding distance for each individual in each front</span>
<span class="keyword">for</span> front = 1 : (length(F) - 1)
<span class="comment">%    objective = [];</span>
    distance = 0;
    y = [];
    previous_index = current_index + 1;
    <span class="keyword">for</span> i = 1 : length(F(front).f)
        y(i,:) = sorted_based_on_front(current_index + i,:);
    <span class="keyword">end</span>
    current_index = current_index + i;
    <span class="comment">% Sort each individual based on the objective</span>
    sorted_based_on_objective = [];
    <span class="keyword">for</span> i = 1 : M
        [sorted_based_on_objective, index_of_objectives] = <span class="keyword">...</span>
            sort(y(:,V + i));
        sorted_based_on_objective = [];
        <span class="keyword">for</span> j = 1 : length(index_of_objectives)
            sorted_based_on_objective(j,:) = y(index_of_objectives(j),:);
        <span class="keywo
(Not finished, please download and read the complete file)
Expand> <Close

Want complete source code? Download it here

Point(s): 1

0 lines left, continue to read
Sponsored links

File list

Tips: You can preview the content of files by clicking file names^_^
Name Size Date
01.96 kB
01.96 kB
tournament_selection.html10.01 kB2006-03-16|16:37
replace_chromosome.html7.98 kB2006-03-16|16:38
objective_description_function.html6.25 kB2006-03-16|16:31
nsga_2.html20.78 kB2006-03-16|16:29
non_domination_sort_mod.html18.88 kB2006-03-16|16:35
initialize_variables.html6.42 kB2006-03-16|16:30
genetic_operator.html14.78 kB2006-03-16|16:30
evaluate_objective.html7.08 kB2006-03-16|16:28
NSGA131.01 kB2006-03-19|20:24
evaluate_objective.m2.16 kB2006-03-16|16:28
genetic_operator.m6.93 kB2009-07-16|10:08
initialize_variables.m3.34 kB2009-07-16|10:09
non_domination_sort_mod.m8.30 kB2009-07-16|10:09
nsga_2.m9.30 kB2009-07-16|10:09
objective_description_function.m3.52 kB2009-07-16|10:09
replace_chromosome.m4.02 kB2009-07-16|10:09
tournament_selection.m4.91 kB2009-07-16|10:09
license.txt1.31 kB2009-07-19|16:16
Sponsored links

non_domination_sort_mod.html (153.84 kB)

Need 1 point
Your Point(s)

Your Point isn't enough.

Get point immediately by PayPal

More(Debit card / Credit card / PayPal Credit / Online Banking)

Submit your source codes. Get more point


Don't have an account? Register now
Need any help?
Mail to:


CodeForge Chinese Version
CodeForge English Version

Where are you going?

^_^"Oops ...

Sorry!This guy is mysterious, its blog hasn't been opened, try another, please!

Warm tip!

CodeForge to FavoriteFavorite by Ctrl+D