Unlike other rules my custom Commerce Fees rule is executing on every cron job I have the following Commerce Fees rule:

{ "rules_setup_fee" : {
    "LABEL" : "Setup Fee",
    "PLUGIN" : "reaction rule",
    "OWNER" : "rules",
    "TAGS" : [ "Commerce License Billing" ],
    "REQUIRES" : [ "rules", "commerce_fees" ],
    "ON" : { "commerce_fees_order" : [] },
    "IF" : [
      { "NOT data_is_empty" : { "data" : [ "commerce-order:commerce-line-items:0:line-item-label" ] } },
      { "AND" : [
          { "text_matches" : {
              "text" : [ "commerce-order:commerce-line-items:0:line-item-label" ],
              "match" : "VS"
            }
          }
        ]
      }
    ],
    "DO" : [
      { "commerce_fees_apply" : {
          "entity" : [ "commerce-order" ],
          "fee" : "setup_fee",
          "amount" : "999",
          "currency_code" : "USD"
        }
      }
    ]
  }
}


which is working just fine, however it is the only rule that shows in the log messages way too frequently:

Type    rules
Date    Thursday, January 14, 2016 - 17:50
User    drupal
Location    http://drupal/admin/config/system/cron
Referrer    http://drupal/admin/config/system/cron
Message Rules debug information:
" Reacting on event Apply a fee to a given order.
0 ms Reacting on event Apply a fee to a given order.
2.988 ms Evaluating conditions of rule Setup Fee. [edit]
3.538 ms The condition data_is_empty evaluated to TRUE [edit]
3.547 ms AND evaluated to FALSE.
3.563 ms Finished reacting on event Apply a fee to a given order.
Severity    notice


It seems like while other rules execute only when necessary, this one does on every cron run. What kind of condition I should add to the rule to make it execute only when someone tries to actually tries to put something in the shopping cart?
I take from the rule export that you're using Commerce License Billing? Well, if you are, then likely it is applying the fees whenever doing it's billing calculations.

Commerce Fees defines it's own rules event that fires off when an order refresh occurs. Order refreshes are done by calling commerce_cart_order_refresh(). When you load an order, a hook_commerce_order_load() gets invoked and commerce_cart has a commerce_cart_commerce_order_load() hook that refreshes orders if certain criteria are met:


The order hasn't been refreshed in this request.
The order is a shopping cart.
The order is the latest revision.
The order can be refreshed. (Commerce 1.9 added new rules to add performance by regulating this better.)


Long story short: It sounds like your install is working fine and in general unless you have thousands of rules firing on every page request, there is little to worry about. Rules are effectively just a wrapper around plan PHP functions. Your cron is running and a new order is being generated or refreshed in some way and so the rule fires.