In[1]:= f = 2 x1 + 3 x2 + 3 y1/2 + 2 y2 - y3/2;
    c = {x1^2 + y1 == 5/4, x2^(3/2) + 3 y2/2 == 3, x1 + y1 <= 8/5, 
       4 x2/3 + y2 <= 3, y3 <= y1 + y2, 0 <= x1 <= 10, 
       0 <= x2 <= 10, -1 <= y1 <= 1, 0 <= y2 <= 1, 
       0 <= y3 <= 1, {y1, y2, y3} \[Element] Integers
       };
    v = {x1, x2, y1, y2, y3};

In[4]:= t1 = 
 Table[AbsoluteTiming[
   NMinimize[{f, c}, v, 
     Method -> {"DifferentialEvolution", "SearchPoints" -> n}][[
    1]]], {n, 2, 10}]

Out[4]= {{0.432374, 8.47632}, {2.24204, 8.47632}, {0.159796, 
  7.66718}, {0.302858, 8.47632}, {0.231295, 7.66718}, {0.155205, 
  8.47632}, {0.350306, 7.93111}, {0.201071, 7.93111}, {0.242186, 
  7.66718}}

In[5]:= t2 = 
 Table[AbsoluteTiming[
   NMinimize[{f, c}, v, 
     Method -> {"RandomSearch", "SearchPoints" -> n}][[1]]], {n, 1, 5}]

Out[5]= {{0.280924, 8.74025}, {0.539471, 8.47632}, {1.20746, 
  8.47632}, {0.784321, 8.24025}, {0.710254, 7.66718}}

In[6]:= (* DifferentialEvolution *)s1 = Style[#, Red] & /@ t1;

In[7]:= (* RandomSearch *) s2 = Style[#, Green] & /@ t2;