decomp.m

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

% function [sub_trees,sub_count,nodes]=decomp(pop)
% 
% Function for decompositioning a population of mathematical expressions
% coded as tree structures. For use with tree_ga2 etc..

% Author             Date     Predecessor   Modification
% ======             ====     ===========   ============
% B.McKay            1/8/95      -    
%
% Function Calls: 
% ==============  
%    
% Last Modification: 18/9/95
% =================
%
 
function [sub_trees,sub_count,nodes]=decomp(pop)

%
% Select each member of the population in turn, and decompose into sub trees
%
[pop_size,L]=size(pop);
temp_pop=pop;


% Define constants as subtrees
% and initialise counting vector  
sub_trees='C';
sub_count=1;
num_sub=1; 
 

  
 for i=1:pop_size 
  disp(i)
   %
   % Count the number of nodes in the tree
   %
   
   x=pop(i,:);
   
   %  Find all constants and convert to 'C'
   % 

   osbr_ind=findstr(x,'[');
   csbr_ind=findstr(x,']');
   num_const=length(osbr_ind);
         
   [L]=length(x);
   
   if num_const~=0,         
      x0=x(1:osbr_ind(1));       
      for j=1:num_const,
         if j==num_const,
            x0 = [x0 'C' x(csbr_ind(j):L)];
         else
            x0 = [x0 'C' x(csbr_ind(j):osbr_ind(j+1))];    
         end
      end
   end
   
   x=x0; 
   
   % I'm not sure how to count UDF's, so for the moment I'll just remove them.
   % Mask (,) ,functions, operators, [ and ] 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
  end
  
  % Count the number of left brackets
  
  obr_ind=findstr(temp_x,'(');
  cbr_ind=findstr(temp_x,')');
  
  nodes(i)=length(obr_ind);


  % Count the number of opperators and functions
  
  struc_complex(i)=0;
  for k=1:length(temp_x), 
     if temp_x(k)=='+' | temp_x(k)=='-' | temp_x(k)=='/' | temp_x(k)=='*' | temp_x(k)=='^' | ...
         temp_x(k)=='r' | temp_x(k)=='s' | temp_x(k)=='l' | temp_x(k)=='p' | ...
        temp_x(k)=='{',
     
        struc_complex(i)=struc_complex(i)+1; 
     end          
  end
  
   
  %
  % Find innermost braket pairs, and extract them if they are "new"
  %  
   
  % 1. Start with left most close bracket, and find first "inner" bracket pair
  % 2. Extract subtree
  % 3. Check if it's already in the list of subtrees
  % 4. Substitue in variable name, and save subtree if required
  % 5. Start again with next close bracket

  p_obr=1;
  p_cbr=1;
  for j=1:nodes(i),

     
           if length(obr_ind) > 1,
              while obr_ind(p_obr+1) < cbr_ind(p_cbr),
                 if p_obr==length(obr_ind)-1,
                    p_obr=p_obr+1;
                    break,
                    end
                 p_obr=p_obr+1;
              end
           end
           
           %if p_obr > 1,
           %   if any(x(obr_ind(p_obr)-1)==['s' 'r' 'l' 'p'])==1,    % Check if sub tree is a function
           %      temp_sub=x(obr_ind(p_obr)-1:cbr_ind(p_cbr)); % Extract
           %      
           %   else
            %     temp_sub=x(obr_ind(p_obr):cbr_ind(p_cbr)); % Extract
            %  end
           %else
              temp_sub=x(obr_ind(p_obr):cbr_ind(p_cbr)); % Extract
           %end
        
           have_num=0;
           for m=1:num_sub,                           % Check if we have it       
              if isempty(findstr(deblank(sub_trees(m,:)),deblank(temp_sub))) < 1,
                 have_num=m;                          % If yes, then record the number
                 sub_count(have_num)=sub_count(have_num)+1; 
                 temp_x=[temp_x(1:obr_ind(p_obr)-1) 'x' num2str(have_num)...
                        temp_x(cbr_ind(p_cbr)+1:length(temp_x))];
                 x=[x(1:obr_ind(p_obr)-1) 'x' num2str(have_num) x(cbr_ind(p_cbr)+1:length(x))];                             
                 break
              end
              
           end % m=1:num_sub,     
           
           if have_num==0,
 
              sub_trees=str2mat(sub_trees,deblank(temp_sub)); % If not then add to collection
              num_sub=num_sub+1;
              sub_count(num_sub)=1;
              temp_x=[temp_x(1:obr_ind(p_obr)-1) 'x' num2str(num_sub)...
                   temp_x(cbr_ind(p_cbr)+1:length(temp_x))]; 
              x=[x(1:obr_ind(p_obr)-1) 'x' num2str(num_sub) x(cbr_ind(p_cbr)+1:length(x))];               
           end
           
        
           obr_ind=findstr(temp_x,'(');               % recalc obr_ind, cbr_ind
           cbr_ind=findstr(temp_x,')');
           p_obr=1;
           p_cbr=1;                
  end               % j=1:nodes(i),
   
   
%   
end    %for i=1:num_pop,
%

%figure(1)
%clg
%hold off
%bar(sub_count)