permut.m

王小平《遗传算法——理论、应用与软件实现》随书光盘

% function [xper]=permut(x,num_inp,fun_set,num_fun_arg_set,fun_name,...
%                           num_fun_arg,user_def_fun)
%
% Permutation (or inversion) opperator. For use with Tree_ga2 etc..

% Author             Date     Predecessor   Modification
% ======             ====     ===========   ============
% B.McKay            3/8/95   mutato3.m     Rewritten to perform permutation
%
% Function Calls: 
% ==============  
%    
% Last Modification: 7/8/95
% =================
%


function [xper]=permut(x,num_inp,fun_set,num_fun_arg_set,fun_name,...
                          num_fun_arg,user_def_fun)

% Randomly pick a position along the string
% and figure out if it is an operator. The 
% chosen element must be a valid 
% operator (not a constant or input).

 [D,L]=size(x);

 x=strrep(x,'[-','[&');
 x=strrep(x,'e+','e@');
 x=strrep(x,'e-','e#'); 
 
 % Find all sockets
         
 osc1_ind=findstr(x,'<');
 csc1_ind=findstr(x,'>');
 type1_ind=osc1_ind+1;
 
 % Mask (, ), functions, operators, and inputs
 % inside UDF's (but not in sockets) 

 temp_x=x;
 
 fo_ind=findstr(x,'{');
 if any(fo_ind)==1,           % If any UDF's
    for j=1:length(fo_ind),
       for k=fo_ind(j):L,
          if x(k)=='+' | x(k)=='-' | x(k)=='/' | x(k)=='*' | x(k)=='^' | ...
             x(k)=='r' | x(k)=='s' | x(k)=='l' | x(k)=='p' | x(k)=='u' | ...
             x(k)=='[' | x(k)==']',    
             temp_x(k)='$';
          elseif x(k)=='<',
             break,
          end
       end
    end
    
    mc_ind=findstr(x,'>');
    for j=1:length(mc_ind),
       for k=mc_ind(j):L,
          if x(k)=='+' | x(k)=='-' | x(k)=='/' | x(k)=='*' | x(k)=='^' | ...
             x(k)=='r' | x(k)=='s' | x(k)=='l' | x(k)=='p' | x(k)=='u' | ...
             x(k)=='[' | x(k)==']',        
             temp_x(k)='$';       
          elseif x(k)=='}' | x(k)=='<',
             break,
          end
       end
    end    
 
   % % Mask [, ] in type I sockets
   % % Mask u's in type II sockets
   % 
   % for j=1:length(osc1_ind),
   %    for k=osc1_ind(j):csc1_ind(j),
   %           if x(k)==']' | x(k)=='[',
   %             temp_x(k)='$';
   %          end
   %       elseif x(type1_ind(j))=='2',
   %          if x(k)=='u',
   %             temp_x(k)='$';
   %          end
   %       elseif x(type1_ind(j))=='3',
   %          break
   %       elseif x(k)=='>',
   %          break,
   %       end
   %    end
   % end 
 end


 sqrt_ind=findstr(temp_x,'r'); sqr_ind=findstr(temp_x,'s');
 exp_ind=findstr(temp_x,'p');  log_ind=findstr(temp_x,'l');
 
 add_ind=findstr(temp_x,'+');  sub_ind=findstr(temp_x,'-');
 mult_ind=findstr(temp_x,'*'); div_ind=findstr(temp_x,'/');
 pow_ind=findstr(temp_x,'^');
 
 udf_ind=findstr(temp_x,'{');
 
 ind =  [add_ind sub_ind mult_ind div_ind pow_ind ...
         sqrt_ind sqr_ind exp_ind log_ind udf_ind];
 
 
flag=0;
[num_fun]=length(ind);

if num_fun==0,
   xper=x;
   xper=strrep(xper,'[&','[-');
   xper=strrep(xper,'e@','e+');
   xper=strrep(xper,'e#','e-');
   return
end



% Select one of the functionals

fun_choice=ceil(rand(1)*num_fun + eps);
i=ind(fun_choice);



%
% Check if functional is from base set or a UDF
%
[HGH1 HGH2]=size(fun_name);
base_fun_flag=any(x(i)==fun_name(1:HGH2));

if base_fun_flag==1,  % Functional is in base set


   % Check number of arguments of functionals
   
   I=findstr(fun_set,x(i));
   num_fun_arg=num_fun_arg_set(I);

   if num_fun_arg==2,
   
      %
      % Extract sub tree 
      %
      
      % Search left

      bo_count=0;
      bc_count=0;

      for j=i:-1:1,
         if x(j) == ')',
            bc_count=bc_count+1;
         elseif x(j) == '(',
            bo_count=bo_count+1;
            if bo_count > bc_count;
               s_point = j;
               break;
            end
         end  
      end

      % Search right

      bo_count=0;
      bc_count=0;

      for j=i+1:L,
         if x(j) == ')',
            bc_count=bc_count+1;
            if bc_count > bo_count;
               e_point = j;
               break;
            end
         elseif x(j) == '(',
            bo_count=bo_count+1;   
         end  
      end

      % take out the relevant string
      
      xstart=x(1:s_point);
      sub_tree=x(s_point+1:e_point-1);
      if e_point == L,
         xend=[')']; 
      else
         xend=x(e_point:L);
      end
 
                      
      %
      % Identify and extract arguments
      %
      
      k=length(xstart);               % Note: num_fun_arg==2
      arg1=x(k+1:i-1);
      arg2=x(i+1:L-length(xend)); 
            
                 
      % Construct sub tree
      sub_tree=['(' arg2 x(i) arg1 ')'];
      
      %
      % Reconstruct the tree
      %
      
      xper=[xstart sub_tree xend];

   else                               % If there is only one argument 
      xper=x;
      xper=strrep(xper,'[&','[-');
      xper=strrep(xper,'e@','e+');
      xper=strrep(xper,'e#','e-');
      return
   
   end

elseif x(i)=='{',    % If selected functional is a UDF


   %
   % Extract sub tree 
   %
   
   % Search right

   bo_count=1;
   bc_count=0;

   s_point=i-1;  
   for j=i+1:L,
      if x(j) == '}',
         bc_count=bc_count+1;
         if bc_count == bo_count;
            e_point = j+1;
            break;
         end
      elseif x(j) == '{',
         bo_count=bo_count+1;   
      end  
   end

   % take out the relevant string
      
   xstart=x(1:s_point);
   sub_tree=x(s_point:e_point);
   if e_point == L,
      xend=[')']; 
   else
      xend=x(e_point:L);
   end
         
   % Mask sockets of any nested UDF's
   
   if bo_count > 1,
      onest_ind=findstr(sub_tree,'{');
      cnest_ind=findstr(sub_tree,'}');
      
      % Search for nested sockets
      nest_sub_tree=sub_tree(onest_ind(2):cnest_ind(length(cnest_ind)-1));
      osnest_ind=findstr(nest_sub_tree,'<') + onest_ind(1);
      csnest_ind=findstr(nest_sub_tree,'>') + onest_ind(1);
      
      % Mask nested sockets
      temp_sub_tree=strrep(sub_tree,'<','$');
      temp_sub_tree=strrep(temp_sub_tree,'>','$');
      
   else
   
      temp_sub_tree=sub_tree;
   end
   
   
   % Find all sockets in old UDF
            
   osc_ind=findstr(temp_sub_tree,'<');
   csc_ind=findstr(temp_sub_tree,'>');
   type_ind=osc_ind+1;                
   
   % Count number of arguments in old UDF
   num_fun_arg=length(osc_ind);
   
   if num_fun_arg > 1, 
         
      %
      % Identify and extract arguments
      %
      
      for j=1:num_fun_arg,      
   eval(['arg' num2str(j) '=sub_tree(type_ind(' num2str(j) ')+2:csc_ind(' num2str(j) ')-2);'])

      end
         
      % Create vector of old argument socket types
      arg_type=str2num(sub_tree(type_ind)');
  

      % 1. Select an argument at random
      % 2. Find out its socket type
      % 3. For type I   => Find all type I sockets and randomly delect one to swap with
      %    For type II  => Find all type II sockets and randomly delect one to swap with
      %    For type III => Find all type III sockets and randomly delect one to swap with
    
   
      % Select an argument at random
      soc_choice=ceil(rand(1)*num_fun_arg + eps);
      soc_type=arg_type(soc_choice);
      arg_type(soc_choice)=0;
      
      if soc_type==1,         
         xper=x;
         xper=strrep(xper,'[&','[-');
         xper=strrep(xper,'e@','e+');
         xper=strrep(xper,'e#','e-');
         return 
      elseif soc_type==2,
         same_type=find(arg_type==2);
      else % if soc_type==3
         same_type=find(arg_type==3);
      end
      
      if same_type==[],
         xper=x;
         xper=strrep(xper,'[&','[-');
         xper=strrep(xper,'e@','e+');
         xper=strrep(xper,'e#','e-');
         return   
      end
      
      same_choice=same_type(ceil(rand(1)*length(same_type) + eps));
      
      % Swap the two arguments
      
      eval(['temp_arg=arg' num2str(soc_choice) ';'])
      eval(['arg' num2str(soc_choice) '=arg' num2str(same_choice) ';'])
      eval(['arg' num2str(same_choice) '=temp_arg;'])
      
      
      % Reconstruct the sub tree
 
         xx=sub_tree;
         sub_tree=xx(2:osc_ind(1)+1);
         keyboard
         for j=1:num_fun_arg,       
            if j~=num_fun_arg,
               sub_tree_new=xx(csc_ind(j):type_ind(j+1));
               eval(['argument=arg' num2str(j)])
               sub_tree=[sub_tree '(' argument ')' sub_tree_new];
                     
            else
               sub_tree_end=xx(csc_ind(j):length(xx)-1);
               eval(['argument=arg' num2str(j)])
               sub_tree=[sub_tree '(' argument ')' sub_tree_end];
            end
         end % Arguments replaced in both sockets       
  
      %
      % Reconstruct the tree
      %
      
      xper=[xstart sub_tree xend];
      
   else
      xper=x;
      xper=strrep(xper,'[&','[-');
      xper=strrep(xper,'e@','e+');
      xper=strrep(xper,'e#','e-');
      return      
   end
   
end

xper=strrep(xper,'[&','[-');
xper=strrep(xper,'e@','e+');
xper=strrep(xper,'e#','e-');


%
% End
%